candy-game-2

There are N toffies in a room labelled from 1 to N and there are  N - 1 directed path between these toffies such that every toffy has at least 1 path leading to the toffy or away from it.

K and L want to eat all the toffies in the room but they don't know where to start.

If K starts with the toffy labelled c (1 ≤ c ≤ N), then he can eat all the toffies which can be reached from the position of the toffy c. Similarly, if L starts with the toffy labelled d (1 ≤ d ≤ N), then he can eat all the toffies which can be reached from the position of the toffy d. Note that both, K and L, can start from the same toffy position.

Now, they will be able to eat all the toffies in the room if there exist toffy positions c and d such that any other toffy in the room can be eaten by at least one of them. In order to make this possible, they want to change the direction of some number of paths. You have to calculate the minimum number of paths that need to be changed so that K and L can eat all the toffies.

Input Format

The first line of input contains the number of toffies, N(1 ≤ N ≤ 3000). Each of the next N-1 lines contains 2 space separated integers ai and bi (1 ≤ ai,bi ≤ N; ai != bi) denoting that there exists a directed path from toffy ai to toffy bi. Toffies are labeled from 1 to N.

Output Format

In the only line of output print the minimum number of paths that need to be changed so that K and L can eat all the toffies.

SAMPLE INPUT
4
1 4
2 4
3 4

SAMPLE OUTPUT
1

Explanation

In the sample case, the graph is such that we need to change at least one path to achieve our target. One of the possible ways is to reverse the path from (1, 4) to (4, 1) and then select C, D as 2, 3 respectively.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: