发现对于一条链，一次操作最多能染黑这条链上的 \(2\) 个点。
所以我们把直径拎出来，设直径长度为 \(d\)。
考虑一条长度为 \(d\) 的链至少要多少次能全染黑。
- 若 \(d\) 为奇数，显然从直径中点 \(u\) 开始做 \((u, 0), (u, 1), \ldots, (u, \frac{d - 1}{2})\) 即可。这样操作次数已经顶到下界了，而且发现由直径的性质，这样能把整棵树都全部染黑。
- 若 \(d\) 为偶数，发现 \(d = 2\) 和 \(d = 4\) 时都需要 \(2\) 次。考虑若 \(d \bmod 4 = 0\)，可以找到直径的中心边 \((x, y)\)，依次做 \((x, 1), (y, 1), (x, 3), (y, 3), \ldots, (x, \frac{d}{2} - 1), (y, \frac{d}{2} - 1)\) 即可，只需 \(\frac{d}{2}\) 次操作。若 \(d \bmod 4 = 2\)，只能做 \((x, 0), (x, 1), \ldots, (x, \frac{d}{2})\)，需要 \(\frac{d}{2} + 1\) 次操作。
找直径即可。时间复杂度 \(O(n)\)，开 \(2 \times 10^3\) 是因为 checker 要 \(O(n^2)\)。
code
// Problem: C. Tree Compass
// Contest: Codeforces - Codeforces Round 934 (Div. 1)
// URL: https://codeforces.com/contest/1943/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 2020;
int n, mxd, U, fa[maxn];
vector<int> G[maxn];
void dfs(int u, int f, int d) {
if (d > mxd) {
mxd = d;
U = u;
}
for (int v : G[u]) {
if (v == f) {
continue;
}
fa[v] = u;
dfs(v, u, d + 1);
}
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
vector<int>().swap(G[i]);
}
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
G[u].pb(v);
G[v].pb(u);
}
mxd = 0;
dfs(1, -1, 1);
mxd = 0;
int s = U;
dfs(U, -1, 1);
int t = U;
vector<int> vc;
for (int i = t; i != s; i = fa[i]) {
vc.pb(i);
}
vc.pb(s);
if ((int)vc.size() % 4) {
printf("%d\n", (int)vc.size() / 2 + 1);
for (int i = 0; i <= (int)vc.size() / 2; ++i) {
printf("%d %d\n", vc[(int)vc.size() / 2], i);
}
} else {
printf("%d\n", (int)vc.size() / 2);
int x = vc[(int)vc.size() / 2 - 1], y = vc[(int)vc.size() / 2];
for (int i = 0; i < (int)vc.size() / 4; ++i) {
printf("%d %d\n%d %d\n", x, i * 2 + 1, y, i * 2 + 1);
}
}
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}