Minequake

문제

The fully autonomous microbreweries installed in the abandoned Dwarven mines of Moravia are truly a testament to the ingenuinity and craftsmanship of Dwarven engineering! Alas, sometimes earthquakes rattle the mines, leading to misaligned pipes and funnels spilling precious liquid on the floor. As the Exalted Warden of Brewery Safety it is your responsibility to turn off the machines in every hall in case of an earthquake.

Walking through tunnels takes time, so you will inevitably arrive late at many of the machines. This cannot be avoided, but you want to minimise the total amount of spilled liquid.

The Dwarven mines consist of $nn$ halls connected by $n-1n-1$ tunnels. The entire system is connected, so it is possible to get from any hall to any of the others. It takes $11$ unit of time to traverse a tunnel. Switching off a machines and traversing a hall takes no time. In each hall, turning off the machines at time $tt$ after the earthquake spills $tt$ liters of liquid. There is exactly one earthquake, the earthquake affects all halls at the same time, and you may not switch off any machines before the earthquake. You can start in any of the halls.

In sample input $11$, the mines look like this:

If you start in hall $22$ and visit the rest of the halls in the order $22$, $11$, $22$, $33$, then you can switch off their machines at time $00$ (in hall $22$), time $11$ (in hall $11$), and time $33$ (in hall $33$). This wastes $0+1+3=40+1+3=4$ liters of liquid in total. If instead you start in hall $11$ and visit the halls in the order $11$, $22$, $33$, the total amount of liquid wasted is $0+1+2=30+1+2=3$ liters, which is better.

입력

The first line of input consists of the integer $nn$, denoting the number of halls. We assume that the halls are numbered $11$, $\dots \backslash ldots$, $nn$. The next $n-1n-1$ lines each contain two space-separated integers $uu$ and $vv$ with , meaning that there is a tunnel between hall $uu$ and hall $vv$.

출력

Print a single integer: the minimum amount of spilled liquid, in liters.

3
1 2
2 3

3

4
1 2
1 3
1 4

7

1

0