发个博客，证明我还活着。
答案很显然，根据 kruskal \text{kruskal} kruskal算法，尽量连 ( i , i + 1 ) (i,i+1) (i,i+1)是最优的，难点在于输出方案。下文设删掉的节点是 v v v。
正常的做法是从小到大依次判断 ( i , i + 1 ) (i,i+1) (i,i+1)是否连通，如果不连通就把这条边加进去，这样可以保证前缀都是联通的，但是发现到 ( v − 1 , v + 1 ) (v-1,v+1) (v−1,v+1)的时候就有问题了，因为这条边不能加进去，这个时候前缀就被分成了两段，直接做就很麻烦了。你可以试一试
这个时候我们可以考虑直接构造，也就是说不用记录这么多信息，并且我们不需要真的去判断这条边加入后是否合法，而是通过一些比较巧妙的方法去确保它合法，这通常需要一些特殊的手段。
考虑求出分开后的每个连通块内编号的最大值 m x mx mx和最小值 m i mi mi。首先我们发现，如果不存在一个连通块的 m i mi mi等于 v + 1 v+1 v+1，那么我们对每个连通块加入 ( m i , m i − 1 ) (mi,mi-1) (mi,mi−1)这条边就是一个合法的构造。证明考虑把连通块按 m i mi mi从小到大排序，这样就得到了一个拓扑序（一定是从下标大的连向下标小的，可以看成一颗树）。
但是如果我们运气不好，恰好存在一个连通块的 m i mi mi等于 v + 1 v+1 v+1，不难发现这个时候只会剩下两个连通块，我们把两个连通块里面编号的最大值求出来，假设其中较小的一个是 m m m，如果 m > v m>v m>v那么连接 ( m , m + 1 ) (m,m+1) (m,m+1)，否则连接 ( v − 1 , v + 1 ) (v-1,v+1) (v−1,v+1)就做完了。这个做法的缺点是要算 i i i在哪颗子树中，要求的信息还是太多了，不够简洁。
其实，还存在更精细的构造，并且只用到了更少的信息和判断。我们考虑把 m i < v mi<v mi<v的连通块分入集合 L L L， m i > v mi>v mi>v的连通块分入 R R R。首先我们判断如果 L L L中 m x mx mx的最大值 t < v t<v t<v，那么用上述构造再连接 ( v − 1 , v + 1 ) (v-1,v+1) (v−1,v+1)即可。考虑对于 L L L中的连通块还是连接 ( m i , m i − 1 ) (mi,mi-1) (mi,mi−1)，但是对于 R R R中的连通块我们要反过来连接 ( m x , m x + 1 ) (mx,mx+1) (mx,mx+1)，原因后面会讲。显然 L L L只会连向 L L L， R R R可能连向 L L L或 R R R。考虑如果 t = n t=n t=n那么此时已经联通了，否则我们直接连 ( t , t + 1 (t,t+1 (t,t+1)就对了。因为我们前面已经保证了 t > v t>v t>v，并且因为 t t t是 L L L中最大的编号，所以 t + 1 t+1 t+1一定在 R R R中，我们发现我们发现这个时候 t + 1 t+1 t+1一定走不到 t t t（编号只会变大），发现这个时候恰好连了 d u v − 1 du_v-1 duv−1条边，所以就对了。感觉最妙的还是想到把点分成两个部分，然后最后一步把最后这条边构造了出来。可以做到线性。
还有一种做法，需要每次加边时判断连通性，但是用到了均摊复杂度的思想。大致思路是分成子树内和子树外两个部分，发现子树内之间的连边只有当 L C A LCA LCA恰好是 v v v的时候才有用，但是 ( i , i + 1 ) (i,i+1) (i,i+1)只有一个 L C A LCA LCA的点，所以就对了。这个技巧也比较实用。
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define db double
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e5+5;
int T,n,rt,sz[N],mi[20][N],mx[20][N],dfn[N],num,fa[N];
vector<int>G[N];
void dfs(int u,int topf){
dfn[u]=++num,mi[0][num]=mx[0][num]=u,sz[u]=1,fa[u]=topf;
for(auto v:G[u]){
if(v==topf)continue;
dfs(v,u),sz[u]+=sz[v];
}
}
int qmin(int l,int r){
if(l>r)return inf;
int k=__lg(r-l+1);
return min(mi[k][l],mi[k][r-(1<<k)+1]);
}
int qmax(int l,int r){
if(l>r)return -inf;
int k=__lg(r-l+1);
return max(mx[k][l],mx[k][r-(1<<k)+1]);
}
int main(){
//freopen("data.in","r",stdin);
// freopen("own.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++)G[i].clear();
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;if(x>y)swap(x,y);
G[x].pb(y),G[y].pb(x);
}
num=0,dfs(1,0);
for(int i=1;i<=__lg(n);i++){
for(int j=1;j<=n-(1<<i)+1;j++){
mi[i][j]=min(mi[i-1][j],mi[i-1][j+(1<<i-1)]);
mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<i-1)]);
}
}
for(int i=1;i<=n;i++){
vector<pair<int,int>>res;
vector<pair<int,int>>L,R;
int ok=0;
for(auto j:G[i]){
if(j!=fa[i]){
pair<int,int>x={qmin(dfn[j],dfn[j]+sz[j]-1),qmax(dfn[j],dfn[j]+sz[j]-1)};
if(x.fi<i)L.pb(x);
else R.pb(x);
}
}
if(i>1){
pair<int,int>x={min(qmin(1,dfn[i]-1),qmin(dfn[i]+sz[i],n)),max(qmax(1,dfn[i]-1),qmax(dfn[i]+sz[i],n))};
if(x.fi<i)L.pb(x);
else R.pb(x);
}
if(i==1){
for(auto e:R){
if(e.fi!=2)res.pb({e.fi,e.fi-1});
}
}
else if(i==n){
for(auto e:L){
if(e.fi!=1)res.pb({e.fi,e.fi-1});
}
}
else{
int tmp=0;
for(auto e:L)tmp=max(tmp,e.se);
if(tmp<i){
for(auto e:L){
if(e.fi!=1)res.pb({e.fi,e.fi-1});
}
for(auto e:R){
if(e.fi!=i+1)res.pb({e.fi,e.fi-1});
}
res.pb({i-1,i+1});
ok=1;
}
else{
for(auto e:L){
if(e.fi!=1)res.pb({e.fi,e.fi-1});
}
for(auto e:R){
if(e.se!=n)res.pb({e.se,e.se+1});
}
if(tmp!=n){
res.pb({tmp,tmp+1});
}
}
}
cout<<res.size()+ok<<" "<<res.size()<<"\n";
for(auto e:res)cout<<e.fi<<" "<<e.se<<"\n";
cout<<"\n";
}
}
}
