M. Matching on a Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Colin recently raised a graph theory problem: MCMMPDNT (Minimum Cost Maximum Matching Problem based on the Depth of Nodes in a Tree).

Given a tree with $$$n$$$ nodes rooted at node $$$1$$$. Define the distance between two nodes as the number of edges on the simple path connecting them. Define the depth of the $$$i$$$-th node as the distance between node $$$i$$$ and the root. It's also guaranteed that, except for depth $$$0$$$, there are an even number of nodes at each depth.

Colin then creates a new undirected graph $$$G$$$ with $$$n$$$ nodes. If node $$$i$$$ and node $$$j\ (i\not=j)$$$ have the same depth on the tree, then there will be an undirected edge in $$$G$$$ connecting node $$$i$$$ and node $$$j$$$, and the weight of that edge is the distance between node $$$i$$$ and node $$$j$$$ on the tree.

For a graph $$$G=(V, E)$$$, a matching $$$M$$$ in $$$G$$$ is a set of pairwise non-adjacent edges; that is, no two edges share common vertices. A maximum matching is a matching that contains the largest possible number of edges. The cost of a matching $$$M$$$ is the sum of the weights of the edges in $$$M$$$. The minimum cost maximum matching is a maximum matching with the minimum cost.

Colin wants to know what the cost of the minimum cost maximum matching in $$$G$$$ is.

Input

The first line contains a single integer $$$n\ (1\le n\le 10^6)$$$, representing the number of nodes on the tree.

For the following $$$n-1$$$ lines, each line contains two integers $$$u_i,v_i\ (1\le u_i, v_i\le n, u_i\not =v_i)$$$, representing an edge of the tree.

It's guaranteed that the input edges form a tree, and except for depth $$$0$$$, there are an even number of nodes at each depth.

Output

A single integer, representing the minimum cost of a maximum matching in $$$G$$$.

Example
Input
7
1 2
1 3
2 4
2 5
2 6
3 7
Output
8
Note

One solution for the minimum cost maximum matching of $$$G$$$ is $$$\{(2,3),(4,5),(6,7)\}$$$, and its cost $$$=2+2+4=8$$$.