#include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 998244353; // constexpr int MOD = 1000000007; constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}; constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; } template inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; int main() { int n; cin >> n; vector> graph(n); REP(_, n - 1) { int u, v; cin >> u >> v; --u; --v; graph[u].emplace_back(v); graph[v].emplace_back(u); } vector>> dp(n); const auto dfs1 = [&](auto dfs1, const int par, const int ver) -> void { if (par != -1) graph[ver].erase(ranges::find(graph[ver], par)); for (const int e : graph[ver]) { dfs1(dfs1, ver, e); int diam = 0; for (const int d : dp[e] | views::elements<1>) chmax(diam, d); if (!dp[e].empty()) chmax(diam, get<0>(dp[e].front())); if (dp[e].size() >= 2) chmax(diam, get<0>(dp[e][0]) + get<0>(dp[e][1])); dp[ver].emplace_back(dp[e].empty() ? 1 : get<0>(dp[e].front()) + 1, diam, e); } if (!dp[ver].empty()) { ranges::sort(dp[ver], greater(), [](const tuple& x) -> int { return get<0>(x); }); } }; dfs1(dfs1, -1, 0); // REP(i, n) { // cout << i + 1 << ':'; // for (const auto& [root, diam, e] : dp[i]) { // cout << " (" << root << ',' << diam << ',' << e + 1 << ')'; // } // cout << '\n'; // } int ans = INF; const auto dfs2 = [&](auto dfs2, const int par, const int ver) -> void { ranges::sort(dp[ver], greater(), [](const tuple& x) -> int { return get<0>(x); }); const int ch = dp[ver].size(); vector from_l(ch, 0), from_r(ch, 0); FOR(i, 1, ch) from_l[i] = max(from_l[i - 1], get<1>(dp[ver][i - 1])); for (int i = ch - 2; i >= 0; --i) { from_r[i] = max(from_r[i + 1], get<1>(dp[ver][i + 1])); } REP(i, ch) { if (get<2>(dp[ver][i]) == par) continue; const int through = [&]() -> int { if (ch == 1) return 0; if (ch == 2) return get<0>(dp[ver][i == 0 ? 1 : 0]); if (i == 0) return get<0>(dp[ver][1]) + get<0>(dp[ver][2]); if (i == 1) return get<0>(dp[ver][0]) + get<0>(dp[ver][2]); return get<0>(dp[ver][0]) + get<0>(dp[ver][1]); } (); const int x = max({from_l[i], from_r[i], through}), y = get<1>(dp[ver][i]); chmin(ans, max({x, y, (x + 1) / 2 + (y + 1) / 2 + 1})); dp[get<2>(dp[ver][i])].emplace_back(ch == 1 ? 1 : get<0>(dp[ver][i == 0 ? 1 : 0]) + 1, x, ver); dfs2(dfs2, ver, get<2>(dp[ver][i])); } }; dfs2(dfs2, -1, 0); // REP(i, n) { // cout << i + 1 << ':'; // for (const auto& [root, diam, e] : dp[i]) { // cout << " (" << root << ',' << diam << ',' << e + 1 << ')'; // } // cout << '\n'; // } cout << ans << '\n'; return 0; }