vada-pav-hunger-2

Nandu and Rani (husband and wife) live in a city consisting of N houses (1, 2, 3, ... , N) and N-1 roads, each road being of length 1 Km and connecting some 2 houses. Moreover, every house is connected to at least one other house. Nandu and Rani live in house 1. 

Nandu is really hungry and wants to eat Vada Pav. Rani, being a caring wife, doesn't want Nandu to spoil his own health. So, she has placed one Vada Pav in each and every house of the city. Nandu has to walk all over the city if he wants to eat those Vada Pavs. Nandu really likes Vada Pavs and decides to eat all of them. However, he doesn't like walking. So he decides he will stay back in the house in which he eats the last Vada Pav.

What is the minimum distance (in Km) Nandu has to travel to eat all the Vada Pavs ?
Input
The first line consists of N. Then, N-1 lines follow, each consisting of 2 space separated integers i and j, denoting that there is a road connecting houses i and j. 
Output
Print a single integer, the minimum distance (in Km) Nandu has to travel to eat all the Vada Pavs.
Constraints
1 ≤ N ≤ 10^3
1 ≤ i, j ≤ N

Author : Shreyans
Tester : Ravi 

SAMPLE INPUT
5
1 2
2 3
1 4
4 5

SAMPLE OUTPUT
6

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: