Description

Original problem from: POJ 3417

Dark is an undirected graph with $N$ nodes and two types of edges: primary edges and additional edges. Dark has $N - 1$ primary edges, and there exists a path composed solely of primary edges between any two nodes in Dark. Additionally, Dark has $M$ additional edges.

Your task is to split Dark into two disconnected parts. Initially, all additional edges of Dark are invincible, and you can only choose to cut one primary edge. Once you cut a primary edge, Dark enters defense mode: the primary edges become invincible, and the additional edges can now be cut. However, your ability allows you to cut only one additional edge in this mode.

Now, you want to know how many different schemes there are to defeat Dark. Note that even if cutting the primary edge alone already splits Dark into two parts, you still need to cut one additional edge to be considered as having defeated Dark.

Input Format

The first line contains two integers $N$ and $M$;

The following $N - 1$ lines each contain two integers $A$ and $B$, indicating a primary edge between $A$ and $B$;

The subsequent $M$ lines provide the additional edges in the same format.

Output Format

Output an integer representing the answer.

Sample 1

4 1
1 2
2 3
1 4
3 4

3

Data Range and Hints

For $20\%$ of the data, $1\le N,M\le 100$;

For $100\%$ of the data, $1\le N\le 10^5,1\le M\le 2\times 10^5$. It is guaranteed that the answer does not exceed $2^{31}-1$.