CF2183D2.Tree Coloring (Hard Version)

This is the Hard version of the problem. The difference between the versions is that in this version, you must find the minimum number of operations and find a way to color the tree using that many operations. You can hack only if you solved all versions of this problem.

You are given a rooted tree$^{\text{∗}}$ consisting of $n$ vertices numbered from $1$ to $n$, where the root has index $1$, and each vertex is initially white. Define $d_i$ as the distance from the root to the $i$-th vertex. You can perform the following operations any number of times:

1. Select a subset $S$ of white vertices such that no two nodes in $S$ are connected by an edge, or have the same distance to node $1$. Formally, $S$ should satisfy for all $x,y\in S$ and $x\neq y$, $d_x\neq d_y$, and there are no edges between $x$ and $y$.
2. Color the vertices in $S$ black.

Your job is to find the minimum number of operations required to color the full tree black and find a way to perform the operations.

$^{\text{∗}}$A tree is a connected graph without cycles. A rooted tree is a tree where one vertex is special and called the root.

这是本题的困难版本。两个版本的区别在于：在本版本中，你不仅要找出所需的最少操作次数，还必须给出一种使用该最少次数完成染色的具体方案。只有当你已解决本题的所有版本后，才可进行 Hack。

给定一棵有根树$^{\text{∗}}$，包含 $n$ 个顶点，编号为 $1$ 到 $n$，其中根节点编号为 $1$，且每个顶点初始均为白色。定义 $d_i$ 为第 $i$ 个顶点到根节点的距离。你可以执行以下操作任意多次：

1. 选择一个白色顶点子集 $S$，使得 $S$ 中任意两个顶点之间既不相邻（即不存在边连接），也不具有相同的到节点 $1$ 的距离。形式化地，对所有 $x,y\in S$ 且 $x\neq y$，需满足 $d_x\neq d_y$，且 $x$ 与 $y$ 之间无边相连。
2. 将子集 $S$ 中的所有顶点染成黑色。

你的任务是：求出将整棵树全部染成黑色所需的最少操作次数，并给出一种实现该最少次数的操作方案。

$^{\text{∗}}$树是一个无环的连通图；有根树是一棵指定某一顶点为根的树。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2\le n\le 2\cdot 10^5$) – the number of vertices in the tree.

The $i$-th following $n-1$ lines contain two integers $u_i$ and $v_i$ ($1\le u_i,v_i\le n$, $u_i\neq v_i$) — the ends of the $i$-th edge.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2\cdot10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2\le n\le 2\cdot 10^5$）——树中顶点的数量。

接下来的 $n-1$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1\le u_i,v_i\le n$，且 $u_i\neq v_i$）——第 $i$ 条边的两个端点。

保证所给的边构成一棵树。

保证所有测试用例的 $n$ 值之和不超过 $2\cdot10^5$。

For each test case:

• Output your number of operations $k$ on the first line ($1 \leq k \leq n$).
• Then, output $k$ lines. Each line should begin with an integer $m$ representing the size of the operation's set ($0 \leq m \leq n$). After that, there should be $m$ numbers $u_1,u_2,\ldots,u_m$ ($1 \leq u_i \leq n$) representing the $m$ nodes you color black in this operation.

You should guarantee that:

• Each operation you make is valid.
• You don't color the same vertex twice (in the same operation or in different operations).
• At the end of all operations, all vertices are colored black.
• The number of operations you performed is $x$, where $x$ is the minimum possible number of operations over all possible solutions.

If there are multiple possible solutions, output any.

对于每个测试用例：

• 在第一行输出你的操作次数 $k$（$1 \leq k \leq n$）；
• 接着输出 $k$ 行，每行首先是一个整数 $m$，表示该次操作所选顶点集合的大小（$0 \leq m \leq n$）；随后是 $m$ 个整数 $u_1, u_2, \ldots, u_m$（$1 \leq u_i \leq n$），表示本次操作中你染成黑色的 $m$ 个顶点。

你需要保证：

• 每次操作均合法；
• 同一顶点不会被重复染色（无论在同一操作内还是在不同操作之间）；
• 所有操作结束后，图中所有顶点均被染成黑色；
• 你执行的操作次数为 $x$，其中 $x$ 是所有可行解中最小可能的操作次数。

若存在多个可行解，输出任意一个即可。

In the first test case, $d_1=1$ and $d_2=d_3=d_4=d_5=2$. We can show that we must perform at least $5$ operations because there are no two nodes that can be operated on simultaneously.

In the second test case, we can show that the least number of operations required to color the full tree is $4$. The example output shows one way to color it in $4$ operations.

在第一个测试用例中，$d_1=1$ 且 $d_2=d_3=d_4=d_5=2$。我们可以证明：由于不存在两个可同时操作的节点，因此至少需要执行 $5$ 次操作。

在第二个测试用例中，我们可以证明：将整棵树完全染色所需的最少操作次数为 $4$。示例输出展示了一种在 $4$ 次操作内完成染色的方法。