#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 namespace __gnu_pbds; typedef tree, rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef long long LL; typedef double D; #define all(v) (v).begin(), (v).end() mt19937 gene(chrono::system_clock::now().time_since_epoch().count()); typedef complex Complex; #define fi first #define se second #define ins insert #define pb push_back inline char GET_CHAR(){ const int maxn = 131072; static char buf[maxn],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxn,stdin),p1==p2)?EOF:*p1++; } inline int getInt() { int res(0); char c = getchar(); while(c < '0') c = getchar(); while(c >= '0') { res = res * 10 + (c - '0'); c = getchar(); } return res; } inline LL fastpo(LL x, LL n, LL mod) { LL res(1); while(n) { if(n & 1) { res = res * (LL)x % mod; } x = x * (LL) x % mod; n /= 2; } return res; } template struct Num { LL a; Num operator + (const Num & b) { return Num{(a + b.a) % mod}; } Num operator - (const Num & b) { return Num{(a - b.a + mod) % mod}; } Num operator * (const Num & b) { return Num{a * b.a % mod}; } Num operator / (const Num & b) { return Num{a * fastpo(b.a, mod - 2, mod) % mod}; } void operator += (const Num & b) {if((a += b.a) >= mod) a -= mod;} void operator -= (const Num & b) {if((a -= b.a) < 0) a += mod;} void operator *= (const Num & b) { a = a * b.a % mod; } void operator /= (const Num & b) { a = a * fastpo(b.a, mod - 2, mod) % mod; } void operator = (const Num & b) { a = b.a; } void operator = (const LL & b) { a = b; } }; template ostream & operator << (ostream & os, const Num & a) { os << a.a; return os; } LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } inline string itoa(LL x, int width = 0) { string res; if(x == 0) res.push_back('0'); while(x) { res.push_back('0' + x % 10); x /= 10; } while((int)res.size() < width) res.push_back('0'); reverse(res.begin(), res.end()); return res; } const int _B = 131072; char buf[_B]; int _bl = 0; inline void flush() { fwrite(buf, 1, _bl, stdout); _bl = 0; } __inline void _putchar(char c) { if(_bl == _B) flush(); buf[_bl++] = c; } inline void print(LL x, char c) { static char tmp[20]; int l = 0; if(!x) tmp[l++] = '0'; else { while(x) { tmp[l++] = x % 10 + '0'; x /= 10; } } for(int i = l - 1; i >= 0; i--) _putchar(tmp[i]); _putchar(c); } typedef double C; struct P { C x, y; void scan() { double _x, _y; scanf("%lf%lf", &_x, &_y); x = _x; y = _y; } void print() { cout << '(' << x << ' ' << y << ')' << endl; } P operator + (const P & b) const { return P{x + b.x, y + b.y}; } P operator - (const P & b) const { return P{x - b.x, y - b.y}; } C operator * (const P & b) const { return x * b.y - y * b.x; } C operator % (const P & b) const { return x * b.x + y * b.y; } }; P operator * (const C & x, const P & b) { return P{x * b.x, x * b.y}; } const int N = 300033; const int LOG = 20; const int mod = 1e9 + 7; const int inf = 1e9 + 7; int n, m; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int rela[N]; int getr(int x) { int p = x; while(rela[p] != p) p = rela[p]; int p1 = p; p = x; while(rela[p] != p) { int p2 = rela[p]; rela[p] = p1; p = p2; } return p1; } int ans = n - 1; vector e[N]; int len[N][2], u[N][2], d[N], up[N], fa[N]; void dfs(int v, int mx) { int maxk[2] = {0, 0}, uk[2] = {0, 0}; for(int y : e[v]) { if(y == fa[v]) continue; int k = d[y]; if(k > maxk[0]) { maxk[1] = maxk[0]; uk[1] = uk[0]; maxk[0] = k; uk[0] = y; }else if(k > maxk[1]) { maxk[1] = k; uk[1] = y; } } for(int y : e[v]) { if(y != fa[v]) { int tmp = up[v]; if(y == u[v][0]) tmp += len[v][1]; else tmp += len[v][0]; int nwmx = max(mx, tmp); nwmx = max(nwmx, y == uk[0] ? maxk[1] : maxk[0]); ans = min(ans, (nwmx + 1) / 2 + 1 + (d[y] + 1) / 2); dfs(y, nwmx); } } } int main() { scanf("%d", &n); ans = n -1 ; for(int i = 1; i < n; i++) { int x, y; scanf("%d%d", &x, &y); e[x].pb(y); e[y].pb(x); } vector q; q.pb(1); for(int op = 0; op < n; op++) { int v = q[op]; for(int y : e[v]) { if(y != fa[v]) { fa[y] = v; q.pb(y); } } } for(int i = n - 1; i >= 0; i--) { int v = q[i]; if(len[v][0] + 1 > len[fa[v]][0]) { len[fa[v]][1] = len[fa[v]][0]; u[fa[v]][1] = u[fa[v]][0]; len[fa[v]][0] = len[v][0] + 1; u[fa[v]][0] = v; }else if(len[v][0] + 1 > len[fa[v]][1]) { len[fa[v]][1] = len[v][0] + 1; u[fa[v]][1] = v; } d[v] = max(d[v], len[v][0] + len[v][1]); d[fa[v]] = max(d[fa[v]], d[v]); } for(int i = 0; i < n; i++) { int v = q[i]; if(v == 1) { up[v] = 0; continue; } up[v] = up[fa[v]] + 1; if(u[fa[v]][0] == v) { up[v] = max(up[v], 1 + len[fa[v]][1]); }else up[v] = max(up[v], 1 + len[fa[v]][0]); } dfs(1, 0); cout << ans << endl; }