Exercise Route

Time limit2sMemory limit512 MB

Summary

Given a spanning tree of N fields plus extra trails, count the simple cycles that use exactly two of the extra trails.

Level: Medium7 of 10
Topics: Tree, Union-find, Sorting
Solved: No attempts yet

Problem

Bessie the cow realizes she needs to exercise more to stay in good shape. She needs help choosing routes around the farm for her morning jogs.

The farm has $N$ fields ( $1 \leq N \leq 2 \cdot 10^5$ ), numbered $1 \ldots N$ , connected by $M$ bidirectional trails ( $1 \leq M \leq 2 \cdot 10^5$ ). The cows usually move between fields along one fixed subset of $N-1$ trails. These are called the standard trails. Using only standard trails, a cow can reach any field from any other field.

Bessie wants a route that uses some non-standard trails, but not many. A good route is a simple cycle (it returns to its starting field and does not visit any field more than once) that contains exactly two non-standard trails. Count the good routes Bessie can take. Two routes are the same if they use the same set of trails.

Input

The first line contains $N$ and $M$ . Each of the next $M$ lines contains two integers $a_i$ and $b_i$ , the endpoints of a trail. The first $N-1$ trails are the standard trails.

Output

Output the number of routes Bessie might want to use.

Examples1

Example 1
Input
```
5 8
1 2
1 3
1 4
1 5
2 3
3 4
4 5
5 2
```
Expected output
```
4
```