J. Good Pairs in Graph and Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree $$$T$$$, and an undirected simple graph $$$G$$$. Both $$$T$$$ and $$$G$$$ have vertices numbered $$$1, 2, \dots, N$$$.

A pair of vertices $$$(u, v)$$$ is called good if the unique path between $$$u$$$ and $$$v$$$ in the tree $$$T$$$ is also a path in $$$G$$$.

Count the number of ordered good pairs $$$(u, v)$$$.

Note that $$$(u, u)$$$ is considered good for all $$$u$$$ (the path of length $$$0$$$).

Input

The first line contains two integers $$$N$$$ and $$$M$$$ $$$(3 \le N, M \le 2 \cdot 10^5)$$$ — the number of vertices and edges in $$$G$$$.

The next $$$N - 1$$$ lines describe the tree $$$T$$$. Each line contains two integers $$$a_i, b_i$$$ $$$(1 \le a_i, b_i \le N)$$$ — an edge of $$$T$$$.

The next $$$M$$$ lines describe the graph $$$G$$$. Each line contains two integers $$$x_i, y_i$$$ $$$(1 \le x_i, y_i \le N)$$$ — an edge of $$$G$$$.

Output

Print a single integer — the number of ordered good pairs $$$(u, v)$$$.

Example
Input
4 3
1 2
2 3
3 4
1 3
3 2
2 4
Output
6
Note

In the example, the good pairs are $$$ (1,1), (2,2), (3,3), (4,4), (2,3), (3,2) $$$. For example, the pair $$$ (1,4) $$$ is not a good pair because the path from 1 to 4 in $$$ T $$$ is $$$ 1-2-3-4 $$$, whereas in $$$ G $$$ it is $$$ 1-3-2-4 $$$, so the paths are different.