#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Int = long long; template ostream &operator<<(ostream &os, const pair &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template ostream &operator<<(ostream &os, const vector &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; } template void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } #define COLOR(s) ("\x1b[" s "m") int N; vector A, B; vector> G; vector pari, dep; vector dis, fin; vector us; void init() { G.assign(N, {}); pari.assign(N, -1); dep.assign(N, 0); dis.assign(N, -1); fin.assign(N, -1); us.clear(); } pair dfs(int u, int pi) { pari[u] = pi; dis[u] = us.size(); us.push_back(u); pair ret(0, u); for (const int i : G[u]) if (pi != i) { const int v = A[i] ^ B[i] ^ u; dep[v] = dep[u] + 1; auto res = dfs(v, i); ++res.first; chmax(ret, res); } fin[u] = us.size(); return ret; } int main() { for (; ~scanf("%d", &N); ) { A.resize(N - 1); B.resize(N - 1); for (int i = 0; i < N - 1; ++i) { scanf("%d%d", &A[i], &B[i]); --A[i]; --B[i]; } init(); for (int i = 0; i < N - 1; ++i) { G[A[i]].push_back(i); G[B[i]].push_back(i); } const auto res0 = dfs(0, -1); const auto res1 = dfs(res0.second, -1); vector U, I; for (int u = res1.second; ; ) { U.push_back(u); const int i = pari[u]; if (!~i) break; I.push_back(i); u ^= A[i] ^ B[i]; } const int K = I.size(); //cerr<<"U = "<