Hide

Problem G
Gotta Catch Em All!

The Kanto region has $N$ junctions and $N - 1$ bidirectional roads. Junctions are numbered from $1$ to $N$, inclusive. All roads have the same length and each of them connects two different junctions.

At any moment, a Pokenom can appear in any of these junctions.

To become the best Pokenom trainer, like no one ever was, Bash is studying the behavior of the Pokenom in Kanto region. Bash has found that, when trying to capture a Pokenom at junction $u$, the Pokenom can run away to junction $v$, iff the optimal path between $u$ and $v$ has length exactly $2$.

More formally, a path of length $K$ from junction $s$ to junction $t$ is an ordered sequence of junctions $v_{0} \rightarrow v_{1} \rightarrow v_{2} \rightarrow \cdots \rightarrow v_{K}$, where $v_{0} = s, v_{K} = t$ and for each valid index $i$, $v_{i}$ and $v_{i+1}$ are connected directly by some road. A path is called optimal iff there is no shorter path with the same starting and ending junctions. Two paths $v_{0} \rightarrow v_{1} \rightarrow \cdots \rightarrow v_{k}$ and $w_{0} \rightarrow w_{1} \rightarrow \cdots w_{l}$ are different iff either $k \neq l$ or there exist some valid $i$ such that $v_{i} \neq w_{i}$.

A Pokenom can use an optimal path of length exactly $2$. Help Bash count the number of such paths.

Input

  • The first line contains one integer $N$ $(1 \leq N \leq 3 \cdot 10^{5})$ — the number of junctions.

  • Each of the rest $N - 1$ lines contains two integers $u$ and $v$ $(1 \leq u, v \leq N, u \neq v)$ — two endpoints of a single road.

Output

  • The only line contains exactly one integer — the number of optimal paths of length $2$.

Explanation for the first example

  • There are two optimal paths of length $2$: $(2 \rightarrow 1 \rightarrow 3)$ and $(3 \rightarrow 1 \rightarrow 2)$.

  • The path $(1 \rightarrow 2 \rightarrow 1)$ is a valid path of length $2$ from $1$ to $1$ but it is not optimal since there is a path of length $0$ from $1$ to $1$.

Sample Input 1 Sample Output 1
3
1 2
1 3
2
Sample Input 2 Sample Output 2
5
2 1
1 5
3 1
4 3
8
Sample Input 3 Sample Output 3
10
1 2
2 3
2 4
1 5
3 6
2 7
7 8
5 9
5 10
24
Sample Input 4 Sample Output 4
8
1 2
2 3
3 4
4 5
5 6
6 1
2 1
12

Please log in to submit a solution to this problem

Log in