#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define int long long int
const int N = 2e1 + 10;
const int md = 1e9 + 7;
const int INF = 1e9;
int32_t main(int32_t argc, char *argv[]) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) {
int n;
cin >> n;
vector<vector<int>> g(n + 1, vector<int> ());
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int x;
for (int i = 1; i <= n; i++)
if ((int) g[i].size() == 1) {
x = i;
break;
}
vector<int> a;
queue<int> q;
vector<bool> visited(n + 1);
q.push(x);
visited[x] = 1;
while (!q.empty()) {
auto u = q.front();
q.pop();
if ((int) g[u].size() == 1)
a.push_back(u);
for (auto v : g[u])
if (!visited[v]) {
q.push(v);
visited[v] = 1;
}
}
cout << (((int) a.size() + 1) >> 1) << '\n';
for (int i = 0; i < (int) a.size() >> 1; i++)
cout << a[i] << " " << a[i + ((int) a.size() >> 1)] << '\n';
if ((int) a.size() & 1)
cout << a[(int) a.size() - 1] << " " << a[0] << '\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... |