P10931 闇の連鎖

The legendary Dark Chain is called Dark by people. Dark is the product of the darkness in the human heart, and heroes from all times and places have tried to defeat it. After research, you find that Dark has the structure of an undirected graph. The graph has $N$ nodes and two types of edges: one type is called main edges, and the other type is called additional edges. Dark has $N - 1$ main edges, and between any two nodes in Dark there exists a path consisting only of main edges. In addition, Dark has $M$ additional edges. Your task is to cut Dark into two disconnected parts. At the beginning, all additional edges of Dark are invincible, and you can only choose one main edge to cut. Once you cut a main edge, Dark will enter defense mode: main edges become invincible, and additional edges can be cut. However, your ability only allows you to cut one more additional edge of Dark. Now you want to know how many different plans can defeat Dark in total. Note that even if after you cut a main edge in the first step you have already split Dark into two parts, you still need to cut one additional edge to count as defeating Dark.

The first line contains two integers $N$ and $M$. Then $N - 1$ lines follow, each line contains two integers $A$ and $B$, indicating that there is a main edge between $A$ and $B$. Then $M$ lines follow in the same format to give the additional edges.

Output one integer representing the answer.

Constraints: $1\le N \le 100000$, $1\le M \le 200000$. The testdata guarantees that the answer does not exceed $2^{31}-1$. Translated by ChatGPT 5