Description

我们有一棵包含 $N$ 个节点的树，这些节点用从 $1$ 到 $N$ 的不同正整数表示。此外，给定树中的 $M$ 对节点，形式为 $(a_1, b_1), (a_2, b_2), \ldots, (a_M, b_M)$。

我们需要为树的每条边指定一个方向，使得对于每一对给定的节点对 $(a_i, b_i)$，存在从 $a_i$ 到 $b_i$ 或从 $b_i$ 到 $a_i$ 的路径。我们需要计算有多少种不同的方法可以实现这一点。由于结果可能非常大，需对 $10^9+7$ 取模。

Input Format

输入的第一行包含正整数 $N$ 和 $M(1 \leq N, M \leq 3 \times 10^5)$，分别表示树中的节点数和给定的节点对数。

接下来的 $N - 1$ 行中，每行包含两个正整数，表示一条边所连接的两个顶点编号。

接下来的 $M$ 行中的第 $i$ 行包含两个不同的正整数 $a_i$ 和 $b_i$，表示第 $i$ 对节点的编号。所有节点对都是互不相同的。

Output Format

你需要输出一个单独的行，包含满足题目要求的树的边的不同方向方法总数，对 $10^9+7$ 取模。

4 1
1 2
2 3
3 4
2 4

4

7 2
1 2
1 3
4 2
2 5
6 5
5 7
1 7
2 6

8

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

0

Hint

数据规模与约定

• 对于 $20\%$ 的数据，满足树是一条链，即 $\forall i<N$，保证 $i$ 和 $i+1$ 有连边。
• 对于另外 $40\%$ 的数据，$1\le N,M\le 5\times10^3$。
• 对于 $100\%$ 的数据，$1\le N,M\le 3\times10^5$。

树的定义：一个包含 $N$ 个节点和 $N-1$ 条边的无向图，满足任两个节点之间都存在一条路径。

题面翻译由 ChatGPT-4o 提供。