在图论中，有根树 $T$ 中两个节点 $v$ 和 $w$ 的最近公共祖先（LCA）是同时拥有 $v$ 和 $w$ 作为后代的最深节点。在此，我们定义每个节点都是其自身的后代。$T$ 中两个节点的 LCA 是它们共同祖先中距离根最远的那一个。

那么，无根树的情况如何呢？

在本题中，给定一棵包含 $n$ 个节点（编号为 $1$ 到 $n$）的无根树 $T$，以及若干对节点 $(v_i, w_i)$。

对于 $T$ 中的每个节点 $x$，考虑以 $x$ 为根的树（此时它成为一棵有根树），并计算总和 $\sum_{i} \text{LCA}(v_i, w_i)$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $t$ ($1 \le t \le 28$)，表示测试数据的组数。

对于每组测试数据，第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 100000$)。接下来的 $n-1$ 行，每行描述一条边，包含两个整数 $v$ 和 $w$ ($1 \le v, w \le n$)。随后 $q$ 行，每行包含一对节点 $(v_i, w_i)$，如上所述 ($1 \le v_i, w_i \le n$)。

输入中 $n$ 的总和与 $q$ 的总和均小于 $1000000$。

输出格式

对于每组测试数据，输出一行，包含 $n$ 个整数。

第 $i$ 个整数表示以第 $i$ 个节点为根时，$\sum_{i} \text{LCA}(v_i, w_i)$ 的值。

样例

样例输入 1

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

样例输出 1

3 5 7 9
1 2 3 4