题目描述

在图论中，有根树 $T$ 中两个节点 $v$ 和 $w$ 的 最近公共祖先 (LCA) 是以 $v$ 和 $w$ 为后代的最深节点。此处我们定义每个节点是自身的后代。$T$ 中两个节点的 LCA 是它们离根最远的公共祖先。

但是，如果是一棵无根树呢？

在本题中，你得到一棵具有 $n$ 个节点（编号从 $1$ 到 $n$）的无根树 $T$，以及若干对节点 $(v_i, w_i)$。

对于 $T$ 的每个节点 $x$，考虑以 $x$ 为根得到的树（成为一棵有根树）；计算求和 $\sum_{i} 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$ 行包含 $q$ 对节点 $(v_i, w_i)$，描述如上 ($1 \le v_i, w_i \le n$)。

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

输出格式

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

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

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

提示

翻译由 DeepSeek V4 Pro 完成