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): x, y = map(int, sys.stdin.readline().split()) adj[x].append(y) adj[y].append(x) # Build the tree structure with parent and children parent = [0] * (N + 1) children = [[] for _ in range(N + 1)] visited = [False] * (N + 1) q = deque([1]) visited[1] = True while q: u = q.popleft() for v in adj[u]: if not visited[v]: visited[v] = True parent[v] = u children[u].append(v) q.append(v) # Iterative post-order traversal post_order = [] stack = [(1, False)] while stack: node, processed = stack.pop() if processed: post_order.append(node) continue stack.append((node, True)) # Push children in reverse order to process left to right for child in reversed(children[node]): stack.append((child, False)) dp = [0] * (N + 1) candidates = [ (0, 0) for _ in range(N + 1) ] # Each node's top two candidates for u in post_order: max1 = -float('inf') max2 = -float('inf') for v in children[u]: c1, c2 = candidates[v] # Update max1 and max2 with c1 if c1 > max1: max2 = max1 max1 = c1 elif c1 > max2: max2 = c1 # Update max1 and max2 with c2 if c2 > max1: max2 = max1 max1 = c2 elif c2 > max2: max2 = c2 # Compute sum_candidates if max1 == -float('inf'): sum_candidates = 0 elif max2 == -float('inf'): sum_candidates = max1 else: sum_candidates = max1 + max2 dp[u] = 1 + sum_candidates # Determine the new candidates for u a = max1 if max1 != -float('inf') else -float('inf') b = max2 if max2 != -float('inf') else -float('inf') c = dp[u] new_candidates = [a, b, c] new_candidates.sort(reverse=True) # Take the first two, replace -inf with -inf c1 = new_candidates[0] if new_candidates[0] != -float('inf') else -float('inf') c2 = new_candidates[1] if len(new_candidates) > 1 and new_candidates[1] != -float('inf') else -float('inf') candidates[u] = (c1, c2) print(dp[1]) if __name__ == '__main__': main()