给你一棵树,其中 $$$n$$$ 个顶点编号为 $$$1, 2, \ldots, n$$$。最初,所有顶点都是白色的。
您可以执行以下两步操作:
1. 选择一个顶点 $$$v$$$ ($$$1 \leq v \leq n$$$) 和距离 $$$d$$$ ($$$0 \leq d \leq n-1$$$)。
2. 对于所有顶点 $$$u$$$ ($$$1 \leq u \leq n$$$) 使得 $$$\text{dist}^\dagger(u,v)=d$$$,颜色 $$$u$$$ 黑色。
构造一个操作序列,使用尽可能少的操作数将树中的所有节点着色为黑色。可以证明,使用最多 $$$n$$$ 操作总是可以做到这一点。
$$$^\dagger$$$ $$$\text{dist}(x, y)$$$ 表示树上顶点 $$$x$$$ 和 $$$y$$$ 之间的(唯一)简单路径上的边数。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 200$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^3$$$) — 树的顶点数。
每个测试用例的以下 $$$n - 1$$$ 行描述了树的边缘。这些行的第 $$$i$$$ 包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$),即第 $$$i$$$ 条边连接的顶点的索引。
保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^3$$$。
输出
对于每个测试用例,首先输出一个整数 $$$op$$$ $$$(1 \le op \le n)$$$,将树的所有顶点着色为黑色所需的最少操作数。
然后,输出 $$$op$$$ 行,每行包含 $$$2$$$ 整数。第 $$$i$$$ 行应包含为第 $$$i$$$ 操作选择的 $$$v$$$ 和 $$$d$$$ 的值 ($$$1 \le v \le n$$$, $$$0 \le d \le n - 1$$$)
您必须保证在$$$op$$$操作结束时,所有顶点都被涂成黑色。
如果有多个解,则可以输出其中任意一个。
示例
输入 #1
4 1 2 1 2 4 1 2 1 3 1 4 7 2 7 3 2 6 4 5 7 1 6 6 7
输出 #1
1 1 0 2 1 1 2 1 2 1 1 2 1 3 6 1 7 1 2 1
注意
在第一个测试用例中,只有一个可能的操作,执行它会给我们一个有效的答案。
在第二个测试用例中,第一个操作将顶点 $$$2$$$ 着色为黑色,第二个操作将顶点 $$$1$$$ 着色为黑色。可以看出,不可能在一次操作中将两个顶点都染成黑色,因此所需的最少操作次数为$$$2$$$。另一种可能的解决方案是使用 $$$2$$$ 运算:$$$(u, r) = (1, 0)$$$ 和 $$$(u, r) = (2, 0)$$$。
在第三个测试用例中,第一个操作将顶点 $$$2$$$、$$$3$$$ 和 $$$4$$$ 着色为黑色,第二个操作将顶点 $$$1$$$ 着色为黑色。再次证明,在 $$$1$$$ 操作中不可能将所有顶点着色为黑色,因此所需的最少操作次数为 $$$2$$$。
在第四个测试用例中,第一个操作将顶点$$$4$$$、$$$1$$$和$$$7$$$着色为黑色,第二个操作将顶点$$$2$$$、$$$5$$$和$$$6$$$着色为黑色,而第三个操作将顶点$$$3$$$和$$$7$$$着色为黑色。请注意,允许将顶点 $$$7$$$ 着色为黑色两次。
因此,每个节点至少被标记一次,其中节点 $$$7$$$ 被标记两次。可以证明,不可能在少于 $$$3$$$ 的时间内将所有顶点着色为黑色。