#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int> adj[N];
vector<int> lf;
void dfs(int u,int p=-1){
if(adj[u].size()==1) lf.push_back(u);
for(auto v:adj[u]){
if(v==p) continue;
dfs(v,u);
}
}
int main(){
int n;
cin>>n;
for(int i=0;i<n-1;i++){
int u,v;
cin>>u >>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1);
int sz=lf.size();
// for(auto tmp:lf){
// cout<<tmp <<" " ;
// }
// cout<<"\n";
cout<<(sz+1)/2 <<"\n";
for(int i=0;i<(sz/2);i++){
cout<<lf[i] <<" " <<lf[i+((sz+1)/2)] <<"\n";
}
if(sz%2) cout<<1 <<" " <<lf[sz/2];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |