题目描述

In graph theory the lowest common ancestor $(LCA)$ of two nodes $v$ and $w$ in a rooted tree $T$ is the deepest node that has both $v$ and $w$ as descendants. Here we define each node to be a descendant of itself. The LCA of two nodes in $T$ is the shared ancestor of them that is located farthest from the root.

But how about an un-rooted tree?

In this problem you are given an un-rooted tree $T$ with $n$ nodes labelled from $1$ to $n$ and several pairs of nodes $(v_i, w_i)$.

For each node $x$ of $T$, consider the tree rooted by $x$ which becomes a rooted tree; and calculate the summation $\sum_{i} LCA(v_i, w_i)$.

输入格式

The input has several test cases and the first line contains an integer $t (1 \le t \le 28)$ which is the number of test cases.

For each test case, the first line contains two integers $n$ and $q (1 \le n, q \le 100000)$. Each of the following $n - 1$ lines describes an edge with two integers $v$ and $w (1 \le v, w \le n)$. Then following $q$ lines contain $q$ pairs of nodes $(v_i, w_i)$ described as above $(1 \le v_i, w_i \le n)$.

Both of the sum of $n$ and the sum of $q$ in input are smaller than $1000000$.

输出格式

For each test case, output a line with $n$ integers.

The $i$-th one is the value of $\sum_{i} LCA(v_i, w_i)$ corresponding to the tree rooted by the $i$-th node.

2
4 3
1 2
1 3
1 4
2 3
3 4
2 4
4 1
1 2
2 3
3 4
1 4

3 5 7 9  
1 2 3 4