注意到一条边无论方向如何，都能使两端的某一个点到达另一个点，即至少有 \(n-1\) 对。如果只需要 \(n-1\) 对，那么只需要在每一条链上相邻的边方向相反即可。对于剩下的一对，我们可以找到一个度数为 \(2\) 的点，并把连接的两条边由反向改为同向，那么附近的三个点产生的对数由 \(2\) 变成了 \(3\)，达到要求（如果度数不为 \(2\)，那么增加的对数一定不止 \(1\)，不能达到要求）。如果找不到则无解。时间复杂度 \(O(\sum n)\)。
#include<iostream>
#include<cstdio>
#include<vector>
#define N 200010
using namespace std;
vector<int> G[N];
int n,rt;
void dfs(int u,int fa,int op){for(auto v:G[u]){if(v==fa)continue;if(op)cout<<u<<' '<<v<<'\n';else cout<<v<<' '<<u<<'\n';dfs(v,u,op^1);}return;
}
void solve(){int u,v;rt=0;cin>>n;for(int i=1;i<=n;i++)G[i].clear();for(int i=1;i<n;i++){cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}for(int i=1;i<=n;i++)if(G[i].size()==2){rt=i;break;}if(!rt){cout<<"NO\n";return;}cout<<"YES\n";cout<<G[rt][0]<<' '<<rt<<'\n';cout<<rt<<' '<<G[rt][1]<<'\n';dfs(G[rt][0],rt,1);dfs(G[rt][1],rt,0);
}
int main(){int T;cin>>T;while(T--)solve();return 0;
}