#include using namespace std; struct Edge { int u; int v; Edge(int a, int b) : u(a), v(b) { } }; using Graph = vector>; vector> dp, dp2, dp_; void dfs(const Graph& G, int v, int p) { for (auto nv : G[v]) { if (nv.v == p) continue; dfs(G, nv.v, v); } int count_ = -1; for (auto c : G[v]) { count_++; if (c.v == p) continue; int count = -1; for (auto d : G[c.v]) { count++; if (d.v == v) continue; //cout << v << " " << c.v << " " << d.v << " " << count << " " << count_ << endl; if (dp[v][count_] < dp[c.v][count] + 1) { dp2[v][count_] = dp[v][count_]; dp[v][count_] = dp[c.v][count] + 1; } else if (dp2[v][count_] < dp[c.v][count] + 1) { dp2[v][count_] = dp[c.v][count] + 1; } } count = -1; dp_[v][count_] = dp[v][count_] + dp2[v][count_]; for (auto d : G[c.v]) { count++; if (d.v == v) continue; dp_[v][count_] = max(dp_[v][count_], dp_[c.v][count]); } } } void dfs2(const Graph& G, int v, int p) { int count_ = -1; for (auto c : G[v]) { count_++; if (c.v == p) { int count = -1; for (auto d : G[c.v]) { count++; if (d.v == v) continue; if (dp[v][count_] < dp[c.v][count] + 1) { dp2[v][count_] = dp[v][count_]; dp[v][count_] = dp[c.v][count] + 1; } else if (dp2[v][count_] < dp[c.v][count] + 1) { dp2[v][count_] = dp[c.v][count] + 1; } } count = -1; dp_[v][count_] = dp[v][count_] + dp2[v][count_]; for (auto d : G[c.v]) { count++; if (d.v == v) continue; dp_[v][count_] = max(dp_[v][count_], dp_[c.v][count]); } } } for (auto nv : G[v]) { if (nv.v == p) continue; dfs2(G, nv.v, v); } } int main() { int N; cin >> N; Graph G(N); vector a(N - 1), b(N - 1), c(N - 1), d(N - 1); for (int i = 0; i < N - 1; i++) { cin >> a[i] >> b[i]; c[i] = G[a[i] - 1].size(); d[i] = G[b[i] - 1].size(); G[a[i] - 1].emplace_back(a[i] - 1, b[i] - 1); G[b[i] - 1].emplace_back(b[i] - 1, a[i] - 1); } dp.assign(N, vector(0)); dp2.assign(N, vector(0)); dp_.assign(N, vector(0)); for (int i = 0; i < N; i++) { dp[i].assign(G[i].size(), 0); dp2[i].assign(G[i].size(), 0); dp_[i].assign(G[i].size(), 0); } dfs(G, 0, -1); dfs2(G, 0, -1); int ans_ = 1000000; for (int i = 0; i < N - 1; i++) { ans_ = min(ans_, (dp_[a[i] - 1][c[i]] + 1) / 2 + (dp_[b[i] - 1][d[i]] + 1) / 2 + 1); } cout << ans_ << endl; }