Mountain Observation Post

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Returning home from the mountains, Zenyk and Marichka decided it would be a good idea to set up a mountain observation post. It needs to be located very high up so they can watch the russians fleeing from Crimea.

Marichka already has a plan according to which there will be \(n\) stone towers, numbered from 1 to \(n\). Zenyk will build each tower using a certain number of stones. He will connect a diesel generator to one of them. He will also use \(n - 1\) yellow-and-blue cables to connect the towers to each other. Cable \(i\) will be connected by its blue end to tower \(a_i\) and by its yellow end to \(b_i\). Any tower will be connected by cables to the generator (possibly through other towers) so that Marichka can comment live on the russian flight.

Looking at the sketch of the observation post, Marichka decided that each cable must always hang correctly to symbolize the Ukrainian flag. That is, for each cable, the tower to which the blue end is connected must be taller than the one to which the yellow end is connected. One tower is taller than another if it is built from a larger number of stones.

Zenyk is trying to figure out how many stones he needs to use to build the observation post. He is no longer young and doesn’t really want to carry heavy stones, which is why he tries to minimize their total number. Note that each tower must be built from at least one stone.

Eventually, Zenyk decided to install another generator. This will allow him to get rid of exactly one of the cables and, possibly, reduce his suffering associated with building the towers. Help Zenyk find the minimum number of stones required to build all the towers.

Input

The first line contains an integer \(n\). Each of the next \(n - 1\) lines contains a pair of integers separated by a space \(a_i\) and \(b_i\).

Output

The minimum number of stones required for construction after removing one of the cables.

Constraints

\(2 \le n \le 10^5\),

\(1 \le a_i, b_i \le n\), each pair of towers is connected by cables (possibly through other towers).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 1 2 1 3 4 1	5

Notes

In the example, it is optimal to get rid of the cable connecting towers 4 and 1. After that, Zenyk will use two stones to build the first tower and one for each of the others.