#include <bits/stdc++.h>
using namespace std;
int n,m,k,q;
vector<int> adj[(int)5e5+5];
vector<int> dep((int)5e5+5);
vector<pair<int,int>> vs;
void dfs(int x, int i){
if(adj[x].size() == 1){
vs.emplace_back(dep[x], x);
return;
}
for(auto to:adj[x]){
if(to == i) continue;
dep[to] = dep[x] + 1;
dfs(to, x);
}
}
int main(){
cin >> n;
for(int i = 2; i <= n; i++){
int a,b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<pair<int,int>> u;
int sz = INT_MAX;
for(int i = 1; i <= n; i++){
vector<pair<int,int>> ans;
vector<int> op;
for(auto to : adj[i]){
dep[to] = 1;
vs.clear();
dfs(to, i);
sort(vs.begin(), vs.end(), greater<pair<int,int>>());
ans.emplace_back(i, vs[0].second);
for(int j = 2; j < vs.size(); j += 2){
ans.emplace_back(vs[j-1].second, vs[j].second);
}
if(vs.size() % 2 == 0){
op.push_back(vs.back().second);
}
}
for(int k = 1; k < op.size(); k += 2){
ans.emplace_back(op[k-1], op[k]);
}
if(op.size() % 2 == 1){
ans.emplace_back(op.back(), i);
}
if(sz > ans.size()){
u = ans;
sz = ans.size();
}
}
cout << u.size() << "\n";
for(auto [a, b] : u){
cout << a << " " << b << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |