/**********************************************************************
* Read a 1-indexed tree, find a centroid, root there, *
* hash the tree “( … child-hashes … )” style (lexicographically *
* sorting the hashes), then perform a second DFS that always visits *
* the child with the smallest hash first. The second DFS records *
* tin / tout / depth arrays and collects all leaves in the order *
* they are first encountered. *
**********************************************************************/
#include <bits/stdc++.h>
using namespace std;
struct TreeHasher {
int n; // number of vertices
vector<vector<int>> g; // 1-indexed adjacency list
vector<int> sz; // subtree sizes
int centroid; // chosen centroid
vector<string> h; // hash of subtree rooted at v
vector<int> tin, tout, depth; // euler timestamps & depths
vector<int> eulerLeaves; // leaves in visit order
int timer = 0;
explicit TreeHasher(int N) : n(N) {
g.assign(n + 1, {});
sz.assign(n + 1, 0);
h.assign(n + 1, "");
tin.assign(n + 1, 0);
tout.assign(n + 1, 0);
depth.assign(n + 1, 0);
}
/*----------------------------------------------------------------*/
/* 1. centroid (classic single pass) */
/*----------------------------------------------------------------*/
void dfsSz(int u, int p) {
sz[u] = 1;
bool isCentroid = true;
for (int v : g[u])
if (v != p) {
dfsSz(v, u);
sz[u] += sz[v];
if (sz[v] * 2 > n) isCentroid = false;
}
if ((n - sz[u]) * 2 > n) isCentroid = false;
if (isCentroid) centroid = u;
}
/*----------------------------------------------------------------*/
/* 2. subtree hash (“canonical form” of unordered rooted tree) */
/*----------------------------------------------------------------*/
string dfsHash(int u, int p) {
vector<string> childHashes;
for (int v : g[u])
if (v != p) childHashes.push_back(dfsHash(v, u));
sort(childHashes.begin(), childHashes.end());
string cur = "(";
for (auto& s : childHashes) cur += s;
cur += ")";
return h[u] = cur;
}
/*----------------------------------------------------------------*/
/* 3. stable-order DFS: children visited in ascending hash order */
/*----------------------------------------------------------------*/
void dfsOrder(int u, int p) {
tin[u] = ++timer;
bool isLeaf = (u != centroid && g[u].size() == 1);
if (isLeaf) eulerLeaves.push_back(u);
// collect & sort children by their already-computed hashes
vector<int> children;
for (int v : g[u]) if (v != p) children.push_back(v);
sort(children.begin(), children.end(),
[&](int a, int b) { return h[a] < h[b]; });
for (int v : children) {
depth[v] = depth[u] + 1;
dfsOrder(v, u);
}
tout[u] = ++timer;
}
/*----------------------------------------------------------------*/
/* Main entry point */
/*----------------------------------------------------------------*/
void process() {
dfsSz(1, 0); // pick centroid
dfsHash(centroid, 0); // hashes with centroid as root
depth[centroid] = 0;
dfsOrder(centroid, 0); // stable-order DFS
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n) || n <= 0) return 0;
TreeHasher TH(n);
for (int i = 0, u, v; i < n - 1; ++i) {
cin >> u >> v;
// u++; v++;
TH.g[u].push_back(v);
TH.g[v].push_back(u);
}
TH.process();
/*-------------------------------------------------------------*/
/* Example output – adjust / remove as you need */
/*-------------------------------------------------------------*/
// cout << "Centroid: " << TH.centroid << '\n';
// cout << "Global hash: " << TH.h[TH.centroid] << '\n';
// cout << "tin:";
// for (int i = 1; i <= n; ++i) cout << ' ' << TH.tin[i];
// cout << "\ntout:";
// for (int i = 1; i <= n; ++i) cout << ' ' << TH.tout[i];
// cout << "\ndepth:";
// for (int i = 1; i <= n; ++i) cout << ' ' << TH.depth[i];
// cout << '\n';
// cout << "Leaves in visit order:";
// for (int v : TH.eulerLeaves) cout << ' ' << v;
// cout << '\n';
deque<int> dd(TH.eulerLeaves.begin(), TH.eulerLeaves.end());
cout << ((TH.eulerLeaves.size() + 1) / 2) << "\n";
cout << dd.front() << " " << dd.back() << "\n";
dd.pop_back(); dd.pop_front();
while (!dd.empty()) {
int c1 = dd.front(); dd.pop_front();
int c2 = dd.front(); dd.pop_front();
cout << c1 << " " << c2 << "\n";
if (dd.size() == 1) {
int c3 = dd.front(); dd.pop_front();
cout << c2 << " " << c3 << "\n";
}
}
}
