题目大意：有一棵n个点的树，初始状态下所有点都是白色的，每次操作可以选择一个点u和一个距离dis，使得距离点u所有长度为dis的点变为黑色，问最少需要多少次操作能使所有点变成黑色，输出所有操作
1<=n<=2000
思路：要想操作数最少，就要使每次操作涂黑的点的数量尽可能多，那么也就是要找这棵树的中心点，而这样的点一定在树的直径上，也就是树上的最长链，直径可以通过两次bfs找最远点或者一次树上dp来找，这里只讲树上dp做法。
经过某个点u的最长链长度应为它的最长子链长度+次长子链长度，所以后序dfs求每个点距离叶子节点的距离的d1[u]维护最长子链的长度，d2[u]维护次长子链的长度，这样直径就等于d1[u]+d2[u]的最大值，记录取得最大值的点为根rt。
知道了直径以后还需要知道直径上的中点，所以在上述过程中用child维护每个点在最长子链中的子节点，这样从rt节点就可以向下找到中点。
如果直径的长度是偶数，也就是直径上有奇数个点，那么中点只有唯一一个，只需要在那个点处操作0到d/2的所有距离即可。
如果直径的长度是奇数，这时中点会有两个，那么如果只用其中一个点操作，操作次数将会是(d+1)/2+1，如果我们分别用两个点交叉操作，可能会出现下面这样的情况：
我们操作4 1 、4 3、5 1、5 3，只需要4次，如果只操作一个中点就需要5次，少一次的原因是我们每次操作都涂黑了至少2个点，只操作一个中点 的话必然会有只涂黑一个点的操作，而要想每次操作都涂黑至少两个点也需要直径的点数是4的倍数，这样才能两个中点交叉操作，所以只需要分两类讨论即可。
//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
typedef long long ll;
const ll MOD = 1e9 + 7;
ll n;
vector<int>g[N];
int d1[N],d2[N];
int child[N];
int d;
int rt;
void init()
{
for (int i = 0; i <= n; i++)
{
g[i].clear();
d1[i] = 0;
d2[i] = 0;
child[i] = 0;
d = 0;
rt = 1;
}
}
void dfs(int u, int fa)
{
for (int i = 0; i < g[u].size(); i++)
{
int v = g[u][i];
if (v == fa)
{
continue;
}
dfs(v, u);
int temp = d1[v] + 1;//当前点到最远的叶子结点的距离
if (temp > d1[u])
{
d2[u] = d1[u];//维护次长子链
d1[u] = temp;//维护最长子链
child[u] = v;//维护最长子链上的子节点关系
}
else if (temp > d2[u])
{
d2[u] = temp;
}
}
if (d1[u] + d2[u] > d)
{//当前点在直径上
d = d1[u] + d2[u];
rt = u;
}
}
void solve()
{
cin >> n;
init();
if (n == 1)
{
cout << 1 << '\n' << 1 << " " << 0 << '\n';
return;
}
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
int dif = d / 2 - d2[rt];//最长链和次长链的差
while (dif)
{
rt = child[rt];//找到中心点
dif--;
}
if (d % 2 == 0 || d1[rt] % 2 == 1)
{//直径长度是偶数或者最长子链长度是奇数（这时候点数一定不是4的倍数），只用一个中点就行
cout << (d - 1) / 2 + 1 + 1 << '\n';
for (int i = 0; i <= d1[rt]; i++)
{
cout << rt << " " << i << '\n';
}
}
else
{//分别用两个中点交叉操作
cout << d / 2 + 1 << '\n';
int temp = d - d1[rt];
int temp2 = temp;
while (temp2>=0)
{
cout << rt << " " << temp2 << '\n';
temp2 -= 2;
}
temp2 = temp;
rt = child[rt];
while (temp2>=0)
{
cout << rt << " " << temp2 << '\n';
temp2 -= 2;
}
}
//cout << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}