思路：
考虑往直径方向想，设直径的长度为 \(d\)。
首先可以注意到一个性质：
- 每次操作最多只会覆盖住直径的 \(2\) 个点，那么答案的下界即为 \(\lceil \frac{d}{2} \rceil\)。
分类讨论一下。
若 \(d\) 为奇数，则存在唯一的一个直径中心 \(u\)：
-
那么答案为 \((u,0),(u,1),\cdots,(u,\lceil \frac{d-1}{2} \rceil)\)。
-
最优次数是 \(\lceil \frac{d}{2} \rceil\) 次。
若 \(d\) 为偶数，则存在两个直径中心 \(u,v\)：
-
若 \(d \bmod 4 = 0\) 时：
-
那么答案为 \((u,1),(v,1),(u,3),(v,3),\cdots,(u,\frac{d}{2}-1),(v,\frac{d}{2}-1)\)。
-
最优次数是 \(\frac{d}{2}\)。
-
这样是两者是完全错开的。
-
-
若 \(d \bmod 4 = 2\) 时：
-
那么答案为 \((u,0),(u,1),\cdots,(u,\frac{2}{d})\)。
-
最优次数是 \(\frac{d}{2}+1\)。
-
这里证明一下为什么当 \(d \bmod 4 = 0\) 时不能取到答案的下界。
注意到若 \(x,y\) 能被同时取到当且仅当 \(\operatorname{dis}(x,y)\) 为偶数。
设 \(L\) 为直径的一个端点，那么 \(\operatorname{dis}(L,x)+\operatorname{dis}(L,y)\) 的奇偶性等价于 \(2*(奇数/偶数)+偶数=偶数\)。
因为 \(d \bmod 4 = 2\)，所以 \(\sum \operatorname{dis}(L,i) = \frac{d \times (d-1)}{2} \bmod 4 = 1\)，则这个和式一定不是偶数，故无法达到下界。
时间复杂度为 \(O(TN)\)。
完整代码：
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=2e3+10;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
ll T,n,x,y,id,sum,cnt;
ll a[N],d[N],fa[N];
vector<ll> E[N];
void add(ll u,ll v){
E[u].push_back(v);
E[v].push_back(u);
}
void dfs(ll u,ll f){
for(auto v:E[u]){
if(v==f)
continue;
fa[v]=u;
d[v]=d[u]+1;
dfs(v,u);
}
}
void solve(){
cnt=0;
n=read();
for(int u,v,i=1;i<n;i++){
u=read(),v=read();
add(u,v);
}
fa[1]=d[1]=sum=0;
dfs(1,1);
for(int i=1;i<=n;i++){
if(d[i]>=sum){
sum=d[i];
id=i;
}
}
//cerr<<id<<'\n';
fa[id]=d[id]=sum=0;
dfs(id,id);
for(int i=1;i<=n;i++){
if(d[i]>=sum){
sum=d[i];
id=i;
}
// cerr<<d[i]<<' ';
}
// cerr<<'\n';
while(id){
a[++cnt]=id;
id=fa[id];
}
if(cnt&1ll){
x=a[(cnt+1)>>1ll];
write((cnt+1)>>1ll);
putchar('\n');
for(int i=0;i<((cnt+1)>>1ll);i++){
write(x);
putchar(' ');
write(i);
putchar('\n');
}
}
else{
x=a[cnt>>1ll],y=a[(cnt>>1ll)+1];
if(cnt&3ll){
write((cnt>>1ll)+1);
putchar('\n');
for(int i=0;i<=(cnt>>1ll);i++){
write(x);
putchar(' ');
write(i);
putchar('\n');
}
}
else{
write(cnt>>1ll);
putchar('\n');
for(int i=1;i<(cnt>>1ll);i+=2){
write(x);
putchar(' ');
write(i);
putchar('\n');
write(y);
putchar(' ');
write(i);
putchar('\n');
}
}
}
for(int i=1;i<=n;i++)
E[i].clear();
}
bool End;
int main(){
T=read();
while(T--)
solve();
cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
return 0;
}