A Winning Strategy in the Black-White Tree Game

The game is played on a tree with n nodes (n ≤ 3\times10^5). Initially, node 1 is colored black and all other nodes are white. Player B starts at node 1. The players then take turns as follows:

• In each round, Player A selects exactly k nodes (regardless of their location) to paint black.
• After that, Player B moves from his current node to an adjacent node.

If, after moving, Player B finds himself on a white node, then Player B wins immediately. Otherwise, if at some point all nodes are black (i.e. Player A has painted every node black), then Player A wins.

Your task is to determine the minimum k such that Player A can guarantee a win regardless of how Player B moves.

Observation: Assume that at the time of a move, Player B is at some node v. The dangerous moves for Player A occur when there are white neighbors adjacent to v that Player B can move into. In order to prevent an immediate win for Player B, Player A must paint all such white neighbors in her move. Notice that when B is at node 1, the number of white neighbors is exactly the degree of node 1; when B is at any other node v, one neighbor (the one from which B came) is already black, so v has at most (deg(v) - 1) white adjacent nodes. Consequently, for Player A to have a winning strategy, it is necessary and sufficient that:

$$k \geq \max\{\; \deg(1),\; \max_{v \neq 1}(\deg(v)-1) \}. $$

In the special case where n = 1, the game is already won by Player A (since all nodes are black), and the answer is 0.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 3×10⁵), the number of nodes in the tree.

Each of the next n − 1 lines contains two integers u and v (1 ≤ u, v ≤ n), representing an undirected edge between nodes u and v.

outputFormat

Print a single integer — the minimum integer k such that Player A can guarantee a win.

sample

1

0

</p>