403534: GYM101191 G Highest ratings year

The mayor of the city Q have recently received a letter from the President about improving ranking cities in the country for the forthcoming «highest ratings» year. The first step is to send the rating of the city, calculated using the new method, to the capital.

The mayor instructed the analytical department to calculate the rating.

There are N monuments situated in city Q, which are numbered from 1 to N and connected by bus routes. It is known that there are exactly N - 1 routes and they allow tourists to pass the way between any pair of monuments (possibly with changes). Let's call function F(A, B) = D (where D is a number of paid bus routes required to get from A up to B) «attractiveness» of the way from the monument A to the monument B.

To attract more tourists and, thereafter, improve the ranking the mayor issued a decree that every second route on the way from the monument A to the monument B is free.

You need to calculate the ranking of the city, which is defined as the sum of paths «attractiveness» between all pairs of monuments.

The first line contains single integer N — the number of monuments in the city of Q (1 ≤ N ≤ 10⁵ ) . Next each of N - 1 lines contains two numbers A_i and B_i — numbers of monuments, among which the bus route pass(1 ≤ A_i, B_i ≤ N, A_i ≠ B_i).

In the single line print a single number — attractiveness of the city Q.

3
1 2
1 3

3

8
1 3
8 1
4 3
5 2
3 6
7 6
5 6

42