Tree Compass（ Codeforces Round 934 (Div. 2) ）

Tree Compass（ Codeforces Round 934 (Div. 2) ）

You are given a tree with $n$ vertices numbered $1,2,\dots ,n$. Initially, all vertices are colored white.

You can perform the following two-step operation:

1. Choose a vertex $v$ ($1\le v\le n$) and a distance $d$ ($0\le d\le n-1$).
2. For all vertices $u$ ($1\le u\le n$) such that ${\text{dist}}^{†}(u,v)=d$, color $u$ black.

Construct a sequence of operations to color all the nodes in the tree black using the minimum possible number of operations. It can be proven that it is always possible to do so using at most $n$ operations.

${}^{†}$ $\text{dist}(x,y)$ denotes the number of edges on the (unique) simple path between vertices $x$ and $y$ on the tree.

Input

Each test contains multiple test cases. The first line contains a single integer $t$ ($1\le t\le 200$) — the number of test cases. The description of the test cases follows.

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

The following $n-1$ lines of each test case describe the edges of the tree. The $i$-th of these lines contains two integers $u_i$ and $v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$), the indices of the vertices connected by 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 does not exceed $2\cdot 10^3$.

Output

For each test case, first output a single integer $op$ $(1\le op\le n)$, the minimum number of operations needed to color all vertices of the tree black.

Then, output $op$ lines, each containing $2$ integers. The $i$-th line should contain the values of $v$ and $d$ chosen for the $i$-th operation ($1\le v\le n$, $0\le d\le n-1$)

You must guarantee that at the end of $op$ operations, all vertices are colored black.

If there are multiple solutions, you may output any one of them.

Example

Input

4121 241 21 31 472 73 26 45 71 66 7

Output

1
1 0
2
1 1
2 1
2
1 1
2 1
3
6 1
7 1
2 1

Note

In the first test case, there is only one possible operation, and performing it gives us a valid answer.

In the second test case, the first operation colors vertex $2$ black, and the second operation colors vertex $1$ black. It can be shown that it is impossible to color both vertices black in one operation, so the minimum number of operations needed is $2$. Another possible solution is to use the $2$ operations: $(u,r)=(1,0)$ and $(u,r)=(2,0)$.

In the third test case, the first operation colors vertices $2$, $3$ and $4$ black, and the second operation colors vertex $1$ black. Again, it can be shown that it is impossible to color all vertices black in $1$ operation, so the minimum number of operations needed is $2$.

In the fourth test case, the first operation colors vertices $4$, $1$ and $7$ black, the second operation colors vertices $2$, $5$ and $6$ black while the third operation colors vertices $3$ and $7$ black. Notice that it is allowed to color vertex $7$ black twice.

Thus, each node was marked at least once, with node $7$ marked twice. It can be shown that it is impossible to color all vertices black in fewer than $3$ moves.

题解进一步分析和拓展

这个问题的关键在于树的直径，即树中两个最远节点之间的路径长度。直径的长度和树的染色策略有很大关系。接下来我们详细分析如何利用直径的性质优化我们的染色操作，并提出最优的染色方案。

一、直径链的染色操作

考虑一条长度为 (d) 的链，链上的每个节点都需要染色，操作一次最多能染黑链上的 2 个点。我们从树的直径出发，考虑如何使用最少的操作将所有节点染黑。

1. 直径 (d) 为奇数

• 当直径 (d) 是奇数时，我们可以选择直径的中点 (u)，然后进行一系列操作，操作的顺序是从 (u) 出发，染色 (u) 和与其距离为 (0, 1, 2, …, d-1) 的节点。这些操作的形式可以是：

  [
  (u, 0), (u, 1), (u, 2), …, (u, d-1)
  ]

  这样，通过最多 ( \frac{d+1}{2} ) 次操作，所有节点都能被染黑，因为每次操作都会把 2 个点染黑。

2. 直径 (d) 为偶数

• 当直径 (d) 为偶数时，我们面临的挑战是如何通过最少次数的操作，覆盖整棵树的所有节点。这里分为两种情况：

  • 当 (d \mod 4 = 0)（即直径长度为 4 的倍数）：
    我们可以选择直径的中心边 ( (x, y) )，然后交替地进行以下操作：

    [
    (x, 1), (y, 1), (x, 3), (y, 3), …, (x, d/2 - 1), (y, d/2 - 1)
    ]

    这样只需要 ( \frac{d}{2} ) 次操作。

  • 当 (d \mod 4 = 2)（即直径长度为 2 或 6 的余数为 2）：
    由于不能完全通过交替操作来染色，我们只能从中心出发，进行如下操作：

    [
    (x, 0), (x, 1), (x, 2), …, (x, d/2)
    ]

    这样需要 ( \frac{d}{2} + 1 ) 次操作。

二、整体思路

1. 找直径：

   • 通过两次 DFS 来找到树的直径。第一次 DFS 从任意节点出发，找到最远的节点 (A)；第二次 DFS 从 (A) 开始，找到最远的节点 (B)，则 (A) 到 (B) 的路径即为树的直径。

2. 根据直径的长度选择操作策略：

   • 如果直径 (d) 为奇数，从中点出发进行操作。
   • 如果直径 (d) 为偶数，分为两种情况：
     • 如果 (d \mod 4 = 0)，通过中心边交替操作。
     • 如果 (d \mod 4 = 2)，从中心出发逐渐染色。

3. 输出操作结果：

   • 输出最少的操作次数和每次操作的具体节点及距离。

三、时间复杂度分析

• DFS 查找直径的时间复杂度是 (O(n))，每次 DFS 都需要遍历整个树的节点和边，最多遍历 (n-1) 条边。
• 操作计算 的时间复杂度是 (O(1))，因为操作次数由直径的长度确定，而直径已经通过 DFS 计算出来。
• 因此，每个测试用例的时间复杂度是 (O(n))，而给定 (T) 个测试用例，所有测试用例的总时间复杂度为 (O(T \cdot n))。题目保证了总节点数 (n) 不超过 2000，所以这是一个高效的解法。

四、代码实现

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 2e3 + 10;int n;
vector<int> g[N];
int fa[N];
int started;
int ended;
int height;
vector<int> rode;void dfs1(int x, int f, int h)
{for (auto it : g[x]){if (it == f){continue;}dfs1(it, x, h + 1);}if (h > height){height = h;started = x;}
}void dfs2(int x, int f, int h)
{fa[x] = f;for (auto it : g[x]){if (it == f){continue;}dfs2(it, x, h + 1);}if (h > height){height = h;ended = x;}
}void cleared()
{for (int i = 0; i <= n; ++i){g[i].clear();fa[i] = 0;}height = 0;rode.clear();
}void solved()
{cin >> n;for (int i = 0; i < n - 1; ++i){int x, y;cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}dfs1(1, 0, 1);// cout << started << endl;height = 0;dfs2(started, 0, 1);int now = ended;while (now != 0){rode.push_back(now);now = fa[now];}// cout << ended << endl;// for (auto it : rode)// {//     cout << it << ' ';// }// cout << endl;if (height % 2 == 1){cout << height / 2 + 1 << endl;for (int i = 0; i <= height / 2; ++i){cout << rode[height / 2] << ' ' << i << endl;}}else if (height % 4 == 0){cout << height / 2 << endl;for (int i = 1; i <= height / 2 - 1; i += 2){cout << rode[height / 2 - 1] << ' ' << i << endl;cout << rode[height / 2] << ' ' << i << endl;}}else{cout << height / 2 + 1 << endl;for (int i = 0; i <= height / 2; i++){cout << rode[height / 2 - 1] << ' ' << i << endl;}}cleared();
}signed main()
{BoBoowen;int T = 1;cin >> T;while (T--){solved();}
}

五、总结

• 树的直径是这道题的核心，利用树的直径来优化染色操作，可以大幅减少操作次数。
• 根据直径的长度，决定从中点出发进行染色或者采用交替操作，这样能够保证染色的最优性。
• 时间复杂度为 (O(n))，对于每个测试用例能够在合理时间内求解出最少的染色操作次数。