#440 Date

Statement

Statement language

Yudam and Woohyun are dating. Worried that Woohyun may be unfaithful, Yudam wants to monitor the places they often visit with CCTV cameras.

The connections between the places form a tree with $N$ vertices and $N-1$ edges. The distance between two vertices $u$ and $v$ is the number of edges on the unique simple path joining them.

Choose a nonnegative integer $B_v$ for every vertex $v$ .

If $B_v=0$ , no CCTV camera is installed at vertex $v$ .
If $B_v\geq 1$ , a CCTV camera of range is installed at vertex . Its cost is , and it monitors every vertex whose distance from is at most .

Find the minimum possible total cost $\sum_{v=1}^{N} B_v$ such that every vertex is monitored by at least one CCTV camera.

Input

The input is given from Standard Input in the following format:

$N$ $u_1\ v_1$ $u_2\ v_2$

Output

Print the minimum total cost required to monitor every vertex.

Constraints

$2\leq N\leq 500\,000$ .
$1\leq u_i,v_i\leq N$ ().

Subtasks

#	Score	Constraints
1	8	$N\leq 8$ .
2	12	The tree is a path.
3	20	$N\leq 500$ .
4	24	$N\leq 5\,000$ .

Samples

Sample 1

Input

Output

1

A CCTV camera of range $1$ at vertex $1$ monitors every vertex.

Sample 2

Input

Output

2

One valid placement uses range- $1$ CCTV cameras at vertices $2$ and $5$ .