#line 2 "lib/prelude.hpp" #ifndef LOCAL #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #endif #include using namespace std; using ll = long long; #define rep2(i, m, n) for (auto i = (m); i < (n); i++) #define rep(i, n) rep2(i, 0, n) #define repr2(i, m, n) for (auto i = (n); i-- > (m);) #define repr(i, n) repr2(i, 0, n) #define all(x) begin(x), end(x) #line 2 "main.cpp" const int MaxN = 1000; int n; vector G[MaxN]; // paths[v] = {(v-u-で始まる最長パス長, u)} 降順 vector> paths[MaxN]; // longest[v] = {(uの部分木内の最長パス長, u)} 降順 vector> longest[MaxN]; int ans; void dfs1(int v, int p) { for (auto u : G[v]) if (u != p) { dfs1(u, v); paths[v].emplace_back(paths[u][0].first + 1, u); longest[v].emplace_back( max(longest[u][0].first, paths[u][0].first + paths[u][1].first), u); } paths[v].emplace_back(0, -1); paths[v].emplace_back(0, -1); sort(paths[v].begin(), paths[v].end(), greater{}); paths[v].resize(3); longest[v].emplace_back(0, -1); sort(longest[v].begin(), longest[v].end(), greater{}); longest[v].resize(2); } void dfs2(int v, int p) { for (auto u : G[v]) if (u != p) { // 辺{u,v}を消す int u_len = max(longest[u][0].first, paths[u][0].first + paths[u][1].first); int i1 = u == paths[v][0].second ? 1 : 0; int i2 = u == paths[v][i1 + 1].second ? i1 + 2 : i1 + 1; int j = u == longest[v][0].second ? 1 : 0; int v_len = max(longest[v][j].first, paths[v][i1].first + paths[v][i2].first); ans = max(ans, u_len + v_len + 2); pair val1(-1, -1), val2(-1, -1); auto it1 = find_if(all(paths[v]), [&](auto&& a) { return a.second == u; }); if (it1 != paths[v].end()) val1 = *it1, paths[v].erase(it1); auto it2 = find_if(all(longest[v]), [&](auto&& a) { return a.second == u; }); if (it2 != longest[v].end()) val2 = *it2, longest[v].erase(it2); paths[u].emplace_back(paths[v][0].first + 1, v); longest[u].emplace_back( max(longest[v][0].first, paths[v][0].first + paths[v][1].first), v); sort(paths[u].begin(), paths[u].end(), greater{}); sort(longest[u].begin(), longest[u].end(), greater{}); dfs2(u, v); if (val1.first != -1) paths[v].insert(it1, val1); if (val2.first != -1) longest[v].insert(it2, val2); } } int main() { scanf("%d", &n); rep(_, n-1) { int u, v; scanf("%d%d", &u, &v), u--, v--; G[u].push_back(v); G[v].push_back(u); } dfs1(0, -1); ans = 0; dfs2(0, -1); printf("%d\n", ans); }