CF2253E.Diameter Intersections

You are given a tree with $n$ vertices. The diameter of a tree is a simple path of maximum length in the tree. The length of a path is the number of edges it contains. The diameter of the given tree has odd length.

We call an integer $k$ beautiful if it is possible to choose two diameters in this tree (possibly with the same endpoints; it is allowed to choose the same two diameters) such that their intersection contains exactly $k$ edges.

Find all beautiful values of $k$ and output them in increasing order.

给你一棵包含 $n$ 个顶点的树。树的直径是指树中长度最大的简单路径。路径的长度定义为该路径所包含的边数。给定树的直径长度为奇数。

我们称一个整数 $k$ 是“优美的”，如果可以在该树中选出两条直径（允许端点相同；也允许选择同一条直径两次），使得这两条直径的交集恰好包含 $k$ 条边。

请找出所有优美的 $k$ 值，并按升序输出。

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case is given in the following format:

• the first line contains one integer $n$ ($2 \le n \le 10^6$) — the number of vertices in the tree;
• the next $n - 1$ lines contain two integers $u$ and $v$ each ($1 \le u, v \le n$, $u \ne v$), denoting an edge between vertices $u$ and $v$.

Additional constraints on the input:

• the sum of $n$ over all test cases does not exceed $10^6$;
• in each test case, the edges form a tree whose diameter has odd length.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的格式如下：

• 第一行包含一个整数 $n$（$2 \le n \le 10^6$）——树中顶点的数量；
• 接下来的 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示顶点 $u$ 与 $v$ 之间存在一条边。

输入的额外约束条件：

• 所有测试用例中 $n$ 的总和不超过 $10^6$；
• 在每个测试用例中，所给边构成一棵树，且该树的直径长度为奇数。

For each test case, print one integer $m$ — the number of beauitful values of $k$; then print the values of $k$ themselves in increasing order.

对于每个测试用例，输出一个整数 $m$ —— 即优美的 $k$ 值的个数；然后按升序输出这些 $k$ 值本身。

Consider the first three examples:

• in the first example, the pair of diameters $(1, 2)$ and $(1, 2)$ gives $k=1$;
• in the second example, the pair of diameters $(1, 4)$ and $(4, 1)$ gives $k=3$;
• in the third example, the pair of diameters $(6, 4)$ and $(3, 5)$ gives $k=1$; the pair of diameters $(6, 4)$ and $(4, 5)$ gives $k=2$; the pair of diameters $(6, 4)$ and $(6, 4)$ gives $k=3$.

考虑前三个例子：

• 在第一个例子中，直径对 $(1, 2)$ 和 $(1, 2)$ 给出 $k=1$；
• 在第二个例子中，直径对 $(1, 4)$ 和 $(4, 1)$ 给出 $k=3$；
• 在第三个例子中，直径对 $(6, 4)$ 和 $(3, 5)$ 给出 $k=1$；直径对 $(6, 4)$ 和 $(4, 5)$ 给出 $k=2$；直径对 $(6, 4)$ 和 $(6, 4)$ 给出 $k=3$。