Background

The hall suddenly became quiet.

"My surname is Yan, given name Shan (Shan)."

His voice was calm and heavy, slightly hoarse but still strong, extremely penetrating. Every word hit the ears hard and seeped into the mind, making it hard not to listen carefully.

"The principal of this academy."

Problem Description

Although Shan is old, he still keeps up with the times. He learned the depth-first search algorithm and felt that this trendy thing would be very popular in a simple and elegant academy. So he found Han, who was wandering in the corridor, and asked him a question:

"We know that performing a depth-first traversal on a tree can be well solved with the following pseudocode."

$$\begin{array}{l} \text{DFS-TREE}(u)\\ \begin{array}{ll} 1 & p\gets p+1\\ 2 & t_p\gets u\\ 3 & vis_u\gets 1\\ 4 & \textbf{for }\text{each edge }(u,v)\in E \\ 5 & \qquad \textbf{if }vis_v=0\\ 6 & \qquad \qquad \text{DFS-TREE}(v)\\ 7 & p\gets p+1\\ 8 & t_p\gets u\\ \end{array} \end{array}$$

Initially, the value of every variable or array is $0$.

"We call the array $t$ obtained during the traversal when calling $\text{DFS-TREE}(1)$ the traversal order of this tree."

"Look at line $4$ of this code: the order in which it iterates over each edge is not fixed."

Han has always hated uncertain things, but out of respect for the principal, he kept listening.

"Can you count how many different traversal orders this code can generate?"

Han realized he had done this problem before and quickly gave the solution. He thought it was over, but Shan continued:

"What if I add one more edge to the tree? Can you still do it?"

Han realized his skill was far from enough, so he went to ask Qi (Qi). Qi thought this problem was still very easy and told Han how to solve it. But Han could not find Shan anymore.

What on earth happened to this world?

Input Format

The first line contains two integers $n$ and $q$, meaning the tree has $n$ nodes, numbered from $1$ to $n$, and there are $q$ queries.

The next $n-1$ lines each contain two integers $u, v$, describing an edge of the tree.

The next $q$ lines each contain two integers $x, y$, meaning an edge connecting $x$ and $y$ is added to the tree, and you need to ask how many traversal orders are possible. Note that each query is independent, i.e., the edge added in the previous query will not be kept for the next query.

Output Format

Output $q$ lines. Each line contains one integer: the answer for this query modulo $10^9+7$.

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

4
6

Hint

Sample Explanation

For the first query, we can get the following graph:

The possible traversal orders are:

• $\{1,2,3,3,2,4,4,1\}$
• $\{1,4,4,2,3,3,2,1\}$
• $\{1,3,2,2,3,4,4,1\}$
• $\{1,4,4,3,2,2,3,1\}$

For the second query, we can get the following graph:

The possible traversal orders are:

• $\{1,2,2,3,3,4,4,1\}$
• $\{1,2,2,4,4,3,3,1\}$
• $\{1,3,3,2,2,4,4,1\}$
• $\{1,3,3,4,4,2,2,1\}$
• $\{1,4,4,2,2,3,3,1\}$
• $\{1,4,4,3,3,2,2,1\}$

Constraints

This problem uses bundled testdata.

Test Point ID	Constraints	Special Property	Score
$\text{Subtask1}$	$n,q\le8$		$5$
$\text{Subtask2}$	$n,q\le20$		$10$
$\text{Subtask3}$	$n,q\le500$
$\text{Subtask4}$	$n,q\le3000$		$15$
$\text{Subtask5}$	$n,q\le2\times10^5$	$\text{A}$
$\text{Subtask6}$		$\text{B}$	$10$
$\text{Subtask7}$			$35$

Special property $\text{A}$: it is guaranteed that in every query, the edge $(x,y)\in E$.

Special property $\text{B}$: it is guaranteed that the tree degenerates into a chain.

For $100\%$ of the data, it is guaranteed that $1\le n,q\le2\times10^5$, $1\le u,v,x,y\le n$, and $x\ne y$.

Translated by ChatGPT 5