Description

Jiutiao Keliang is a girl who likes patterns. By this pattern, the second problem should be related to data structures.

In a distant kingdom, there are $n$ cities. There are $n - 1$ bidirectional roads between the cities, and these roads guarantee that any two cities can reach each other directly or indirectly.

In ancient times, these $n$ cities were at war with each other. In a highly isolated environment, each city developed its own language. After the kingdom was unified, language barriers greatly hindered the kingdom’s development. To improve this, the king ordered the design of $m$ common languages and carried out $m$ language unification operations. In the $i$-th operation, a minister started from city $s_i$, walked to $t_i$ along the shortest path, and taught every city on the way (including $s_i$ and $t_i$) to use the $i$-th common language.

Once there is a shared language, cities can conduct trade. Two cities $u_i, v_i$ can conduct trade if and only if there exists a common language $L$ such that every city on the shortest path from $u_i$ to $v_i$ (including $u_i$ and $v_i$) can use $L$.

To measure the effect of the language unification operations, the king wants you to compute how many pairs of cities $(u, v)$ with $u < v$ can conduct trade.

Input Format

The first line contains two positive integers $n, m$, representing the number of cities and the number of common languages.

The next $n - 1$ lines each contain two integers $x_i, y_i$ ($1 \le x_i, y_i \le n$), indicating a road connecting cities $x_i$ and $y_i$.

The next $m$ lines each contain two integers $s_i, t_i$ ($1 \le s_i, t_i \le n$), indicating one language promotion operation.

Output Format

Output one line with one integer, representing the number of pairs of cities that can conduct trade.

5 3
1 2
1 3
3 4
3 5
3 4
1 4
2 5

8

Hint

Sample Explanation

The pairs of cities that can conduct trade are $(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5)$.

Constraints

For $100\%$ of the testdata, $1 \le x_i, y_i, s_i, t_i \le n\leq 10 ^ 5$, $1\leq m\leq 10 ^ 5$, and $x_i\neq y_i$.

Translated by ChatGPT 5