Migrated from Lutece 2717 Color the Tree

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Kazuhime finds a tree on the ground and she wants to give it to Wang Jiro.

But the tree looks too drab, so Kazuhime decides to paint every edge of the tree a kind of color.

In particular, Kazuhime hopes that for each point, the colors of all the connected edges are different from each other, because this may be more in line with Wang Jiro's aesthetic.

The cost of coloring an edge with color $i$ is $i$, Kazuhime wants to know the minimum cost.

Input

The first line is a positive integer $n \ (n\le150)$, representing the number of points in the tree.

The next $n-1$ lines each have two positive integers $s,t$, representing an edge connecting the point numbered $s$ to the point numbered $t$.

Output

Output a number for the minimum cost.

Samples

5
1 2 
1 3 
2 4 
2 5

7

Resources

2022 UESTC ICPC Training for Graph