from itertools import combinations from heapq import heappop,heappush from collections import deque class Const_Tree(): def __init__(self,N) -> None: self.const_edge = [[] for _ in range(N)] self.parent = [-1 for _ in range(N)] self.rev_edge = [[] for _ in range(N)] self.q = deque() self.edge = [[] for _ in range(N)] self.N = N def add_edge(self,u,v): self.edge[u].append(v) def const(self,st): self.q.append(st) seen = [False for _ in range(self.N)] while self.q: now = self.q.popleft() seen[now] = True for next in self.edge[now]: if not seen[next]: self.q.append(next) self.const_edge[now].append(next) self.parent[next] = now self.rev_edge[next].append(now) self.q = deque() self.parts = [1 for _ in range(self.N)]#部分木の数 for i in range(self.N): if len(self.const_edge[i]) == 0: self.q.append(i) self.cnt = [0 for _ in range(self.N)] while self.q: now = self.q.popleft() for next in self.rev_edge[now]: self.parts[next] += self.parts[now] self.cnt[next] += 1 if self.cnt[next] == len(self.const_edge[next]): self.q.append(next) def topological_sort(G): ret = [] start = [] par_count = [0] * len(G) for u in range(len(G)): for v in G[u]: par_count[v] += 1 for v in range(len(G)): if par_count[v] == 0: start.append(v) while start: u = start.pop() ret.append(u) for v in G[u]: par_count[v] -= 1 if par_count[v] == 0: start.append(v) if any(c > 0 for c in par_count): # G is not a DAG return None return ret N = int(input()) ct = Const_Tree(N) for _ in range(N-1): u,v = map(int,input().split()) u-=1 v-=1 ct.add_edge(u,v) ct.add_edge(v,u) ct.const(0) edge = ct.const_edge P = ct.parent downmemo = [[] for _ in range(N)] down = [0] * N up = [0] * (N) upsub = [0] * N tp = topological_sort(edge) dlen = [1] * N def f(List,c): tmp = [] while List: x,u = heappop(List) tmp.append((x,u)) for x,u in tmp: heappush(List,(x,u)) if len(List) <=1: return 0 elif len(List) == 2: for x,u in tmp: if u != c: return -x elif len(List) ==3: for i,k in combinations([l for l in range(3)],2): if tmp[i][1] != c and tmp[k][1] != c: return -tmp[i][0] - tmp[k][0] - 1 def g(List): tmp = [] while List: x,u = heappop(List) tmp.append((x,u)) for x,u in tmp: heappush(List,(x,u)) if len(List) == 0: return 1 elif len(List) == 1: return -tmp[0][0] elif len(List) >=2: return -tmp[0][0] - tmp[1][0] -1 def m(List,c): tmp = [] while List: x,u = heappop(List) tmp.append((x,u)) for x,u in tmp: heappush(List,(x,u)) if len(List) == 0: return 0 if len(List) == 1: return 1 else: for x,u in tmp: if u != c: return -tmp[0][0] for u in tp[::-1]: for cu in edge[u]: dlen[u] = max(dlen[cu]+1,dlen[u]) heappush(downmemo[u],(-dlen[cu]-1,cu)) if len(downmemo[u]) > 3: tmp = [] for _ in range(3): x,u1 = heappop(downmemo[u]) tmp.append((x,u1)) while downmemo[u]: x,u1 = heappop(downmemo[u]) for x,u1 in tmp: heappush(downmemo[u],(x,u1)) for cu in edge[u]: up[cu] = max(f(downmemo[u],cu),up[cu]) for u in tp: up[u] = max(upsub[u],up[u]) for cu in edge[u]: upsub[cu] = max(m(downmemo[u],cu),upsub[cu]) up[cu] = max(up[u],up[cu]) upsub[cu] = max(upsub[cu],upsub[u] + 1) ans = [0] * N for u in range(N): down[u] = max(g(downmemo[u]) , down[u]) if up[u] != 0 : ans[u] = (up[u]+1)//2 + (down[u] + 1)//2 else: ans[u] = down[u]-1 print(min(ans))