In the lawn of KOI Park, there is an anthill where many ants live together. It consists of $N$ rooms and $N-1$ passages directly connecting distinct rooms, and any two distinct rooms are reachable through passages. Thus, the anthill is a tree with $N$ vertices. Each room is numbered from $1$ to $N$.

Each room can house at most one ant. If the rooms housing two ants are directly connected by a passage, those ants feel uncomfortable with each other. Therefore, at present, at most one of the two rooms connected by each passage is occupied.

The ants are clever, so the anthill currently houses as many ants as possible subject to this condition. In other words, if one more ant entered, no arrangement of the ants in the rooms could satisfy the condition.

On a sunny summer day, many people picnic at KOI Park. As they picnic on the lawn, the soil forming the anthill crumbles and exactly one new passage connecting two distinct rooms appears. The two rooms may already be directly connected. In other words, for any two integers $1 \le i < j \le N$, a new passage between rooms $i$ and $j$ may appear, regardless of whether such a passage existed before.

This new passage may directly connect rooms occupied by two ants, making that pair uncomfortable. The ants currently living in the anthill may therefore have to rearrange themselves to satisfy the condition. Depending on the choice of $(i,j)$, this may be possible, but in some cases no rearrangement of all current ants satisfies the condition. In such cases, some resident ants may have to be evicted.

For two integers $1 \le i < j \le N$, call $(i,j)$ a peaceful pair if, when a passage connecting rooms $i$ and $j$ is added, all ants can satisfy the condition by rearranging themselves without evicting anyone. Given the anthill structure, count the peaceful pairs.

Constraints

• $2 \le N \le 250\,000$
• $u \ne v$, $1 \le u,v \le N$
• The given anthill has a tree structure.

Subtasks

1. (8 points) $N \le 16$.
2. (6 points) $N \le 80$.
3. (18 points) $N \le 400$.
4. (18 points) $N \le 2000$.
5. (6 points) $N \le 10000$.
6. (8 points) $N \le 50000$.
7. (36 points) No additional constraints.

Input

The first line contains $N$.

The next $N-1$ lines each contain the numbers $u$ and $v$ of the two rooms connected by a passage.

Output

Print the number of peaceful pairs on the first line.

Examples

Input 1

4
1 2
1 3
1 4

Output 1

3

Note

Initially, at most 3 ants can live in the anthill, and the only possible arrangement with that many ants is $\{2,3,4\}$. Adding a passage between already directly connected rooms does not require rearrangement. There are 3 such cases. In every other case, no arrangement can house 3 ants after the passage is added.

Input 2

6
1 2
2 3
3 4
4 5
5 6

Output 2

15

Note

Initially, at most 3 ants can live in the anthill, and one possible arrangement is $\{1,3,6\}$. Whatever passage is added, there is an arrangement that can house 3 ants.

Input 3

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

Output 3

11