import sys from collections import deque def main(): sys.setrecursionlimit(1 << 25) N = int(sys.stdin.readline()) adj = [[] for _ in range(N + 1)] for _ in range(N - 1): u, v = map(int, sys.stdin.readline().split()) adj[u].append(v) adj[v].append(u) def find_farthest(start): visited = [-1] * (N + 1) q = deque([start]) visited[start] = 0 max_dist = 0 far_node = start while q: u = q.popleft() for v in adj[u]: if visited[v] == -1: visited[v] = visited[u] + 1 q.append(v) if visited[v] > max_dist: max_dist = visited[v] far_node = v return far_node, visited s, _ = find_farthest(1) t, dist_s = find_farthest(s) s_new, dist_t = find_farthest(t) assert s_new == s # To confirm t is farthest from s parent = [0] * (N + 1) q = deque([s]) parent[s] = -1 while q: u = q.popleft() for v in adj[u]: if parent[v] == 0 and v != parent[u]: parent[v] = u q.append(v) if v == t: q = deque() # Break early break path = [] u = t while u != s: path.append(u) u = parent[u] path.append(s) path = path[::-1] D = len(path) - 1 d = [0] * (D + 1) for i in range(D + 1): current = path[i] prev_node = path[i - 1] if i > 0 else None next_node = path[i + 1] if i < D else None branches = [] for v in adj[current]: if v != prev_node and v != next_node: branches.append(v) if not branches: d[i] = 0 continue visited = {current} max_depth = 0 q = deque() for b in branches: q.append((b, 1)) visited.add(b) max_depth = max(max_depth, 1) while q: u_node, depth = q.popleft() for v in adj[u_node]: if v not in visited and v != current: visited.add(v) new_depth = depth + 1 if new_depth > max_depth: max_depth = new_depth q.append((v, new_depth)) d[i] = max_depth max_left = [0] * (D + 1) max_left_sub = [0] * (D + 1) current_max = d[0] + 0 current_max_sub = d[0] - 0 max_left[0] = current_max max_left_sub[0] = current_max_sub for i in range(1, D + 1): current_max = max(current_max, d[i] + i) current_max_sub = max(current_max_sub, d[i] - i) max_left[i] = current_max max_left_sub[i] = current_max_sub max_right = [0] * (D + 1) max_right_sub = [0] * (D + 1) current_max = d[D] + D current_max_sub = d[D] - D max_right[D] = current_max max_right_sub[D] = current_max_sub for i in range(D - 1, -1, -1): current_max = max(current_max, d[i] + i) current_max_sub = max(current_max_sub, d[i] - i) max_right[i] = current_max max_right_sub[i] = current_max_sub min_candidate = float('inf') for i in range(D): len1 = i sum1 = max_left[i] + max_left_sub[i] diam1 = max(len1, sum1) len2 = D - (i + 1) if i + 1 > D: sum2 = 0 else: sum2 = max_right[i + 1] + max_right_sub[i + 1] diam2 = max(len2, sum2) radii1 = (diam1 + 1) // 2 radii2 = (diam2 + 1) // 2 candidate = max(diam1, diam2, radii1 + radii2 + 1) if candidate < min_candidate: min_candidate = candidate print(min_candidate) if __name__ == '__main__': main()