403534: GYM101191 G Highest ratings year

Memory Limit:64 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Highest ratings yeartime limit per test1 secondmemory limit per test64 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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

ExamplesInput
3
1 2
1 3
Output
3
Input
8
1 3
8 1
4 3
5 2
3 6
7 6
5 6
Output
42

加入题单

上一题 下一题 算法标签: