#include <bits/stdc++.h>
int main() {
int n;
std::cin >> n;
std::vector<int> adj[n + 1];
for(int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int timer = 1;
std::vector<int> in(n + 1);
std::function<void(int, int)> dfs = [&] (int v, int p) {
in[v] = timer++;
for(auto u : adj[v]) {
if(u == p) {
continue;
}
dfs(u, v);
}
};
dfs(1, 0);
std::vector<std::pair<int, int>> ans;
std::vector<std::pair<int, int>> l;
for(int i = 1; i <= n; i++) {
if(adj[i].size() == 1) {
l.push_back({in[i], i});
}
}
std::sort(l.begin(), l.end());
int L = l.size();
for(int i = 0; i < l.size() && ans.size() < (L + 1) / 2; i++) {
ans.push_back({l[i].second, l[(i + L / 2) % L].second});
}
std::cout << ans.size() << "\n";
for(int i = 0; i < ans.size(); i++) {
std::cout << ans[i].first << " " << ans[i].second << "\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... |