прогулка по мостам

Задача E1. Прогулка по мостам

Возможно вы знаете историю про то, как Эйлер гулял по мостам Кёнигсберга. Допустим теперь, что Эйлер попал на некий архипелаг, между некоторыми островами которого имеются мосты. Мосты построены таким образом, что между любыми двумя островами архипелага можно построить путь по этим мостам, причем этот путь единственный. Все острова пронумерованы от 1

1 до n

n. Эйлер находится на острове номер 1

1 и желает совершить следующую прогулку: с острова номер 1

1 он хочет дойти до острова номер 2

2, далее до острова номер 3

3 и так далее до острова номер n

n. С него он хочет вернуться на остров номер 1

1. Он прекрасно понимает, что при этом ему придётся посещать некоторые мосты по многу раз. Осталось выяснить, сколько раз суммарно он пройдет по мостам во время своей прогулки.

Формат входных данных

В первой строке содержится число n

n - количество островов в архипелаге, 2 \leq n \leq 10^3

2≤n≤103

. В следующих n-1

n−1 строках содержатся по два числа a_i

ai

 и b_i

bi

 через пробел - номера островов, соединённых мостом, 1 \leq a_i, b_i \leq n, a_i \neq b_i

1≤ai

,bi

≤n,ai



=bi

. Гарантируется, что между любыми двумя островами архипелага можно построить путь по этим мостам, причем этот путь единственный.

Формат выходных данных

Вывести длину описанного пути, то есть суммарное количество пересечений мостов, которые придётся совершить.

Пояснение к примеру

На рисунке вы видите расположение мостов в архипелаге из примера. Прогулка Эйлера будет проходить следующим образом:

1 - 5 - 8 - 2 : 3 моста

2 - 8 - 5 - 1 - 3 : 4 моста

3 - 1 - 5 - 4 : 3 моста

4 - 5 : 1 мост

5 - 8 - 6 : 2 моста

6 - 8 - 5 - 7 : 3 моста

7 - 5 - 8 : 2 моста

8 - 5 - 1 : 2 моста.

Итого он пройдет через 3 + 4 + 3 + 1 + 2 + 3 + 2 + 2 = 20 мостов.

Sample Input:

8

5 8

1 3

8 6

7 5

2 8

1 5

4 5

Sample Output:

20