P16820 [HackerEarth] 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 hou
普及
题目描述

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

输入格式

见题面

输出格式

见题面

样例输入
100 91 1 31 91 71 31 23 31 59 1 80 1 86 31 33 86 89 23 20 86 75 1 87 23 24 59 47 71 83 89 15 20 58 1 12 71 73 31 70 91 67 86 94 12 40 31 77 87 66 24 17 75 62 94 26 66 27 12 69 40 22 75 68 73 92 94 51 80 43 92 4 92 63 1 8 24 2 83 37 1 48 73 5 80 90 89 64 91 57 92 6 37 52 23 42 87 41 62 36 12 30 8 84 5 39 48 82 30 60 64 95 77 65 5 99 73 74 70 21 63 11 60 18 33 44 30 25 21 32 75 50 71 98 30 97 33 81 33 34 52 61 24 78 31 19 22 35 74 96 5 38 87 100 25 46 11 28 75 45 17 29 44 79 17 49 67 85 57 72 1 10 36 14 87 93 29 9 60 13 82 3 32 7 11 56 49 76 27 53 97 54 13 55 57 16 92 88 77
样例输出
190