Daejeon Urban Railway Line 2

Interview

Time limit1sMemory limit1024 MB

Summary

Count unordered pairs of intersections off the 1-to-N path whose tree path touches that path at least once.

Level: Medium4 of 10
Topics: Tree, DFS, Combinatorics
Solved: No attempts yet

Problem

Daejeon has $N$ intersections and $N-1$ roads that form a tree. The intersections are numbered from $1$ to $N$ . Daejeon runs Urban Railway Line 1 along the path that connects intersection $1$ and intersection $N$ . Stations are installed at the intersections on this path, and rails are installed on the roads on it.

The city plans to run an additional Line 2. As with Line 1, Line 2 will have stations and rails along the path that connects intersection $S$ and intersection $E$ . Intersections $S$ and $E$ must be different and must not have Line 1 stations. Line 2 must include at least one Line 1 station so that riders can transfer to Line 1.

Count the number of ways to choose two intersections that satisfy these conditions. Two choices that differ only in order are considered the same.

Input

The first line contains an integer $N$ ( $4 \le N \le 100000$ ). The next $N-1$ lines each contain $u$ and $v$ ( $1 \le u, v \le N$ ; $u \ne v$ ), the endpoints of a road, separated by a space.

Output

Print the number of ways to choose two intersections that satisfy the conditions.

Examples3

Example 1
Input
```
4
2 1
1 4
4 3
```
Expected output
```
1
```
Example 2
Input
```
4
1 4
4 2
2 3
```
Expected output
```
0
```
Example 3
Input
```
7
1 2
2 3
1 4
1 5
5 6
5 7
```
Expected output
```
5
```