#include <bits/extc++.h>
using namespace std;
typedef long long ll;
vector<int> g[500010], leaves;
void dfs(int no, int pa) {
if(g[no].size() == 1) {
leaves.push_back(no);
}
for(auto i: g[no]) {
if(i == pa) continue;
dfs(i, no);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1, 0);
int l=leaves.size();
int m=l/2;
vector<pair<int,int>> ans;
for(int i=0;i<m;i++){
ans.emplace_back(leaves[i], leaves[i+m]);
}
if(l%2){
ans.emplace_back(leaves[0], leaves[l-1]);
}
cout<<ans.size()<<"\n";
for(auto &p: ans){
cout<<p.first<<" "<<p.second<<"\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |