题目描述

我们有一棵包含 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$ 取模。

输入格式

输入的第一行包含正整数 N 和 M（$1 \leq N, M \leq 3 \times 10^5$），分别表示树中的节点数和给定的节点对数。接下来的 N - 1 行中，每行包含两个正整数，表示通过一条边连接的节点的标签。接下来的 M 行中的第 $i$ 行包含两个不同的正整数 $a_i$ 和 $b_i$，表示第 $i$ 对节点的标签。所有节点对都是互不相同的。

输出格式

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

输入输出样例 #1

输入 #1

4 1
1 2
2 3
3 4
2 4

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

8

输入输出样例 #3

输入 #3

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

输出 #3

0

说明/提示

在占总分 20% 的测试用例中，给定的树将是一个链。换句话说，对于所有 $i < N$，节点 $i$ 将通过一条边连接到节点 $i + 1$。在额外的占总分 40% 的测试用例中，将满足 $N, M \leq 5 \times 10^3$。树是一个包含 N 个节点和 N - 1 条边的图，使得每个节点到其他节点都存在路径。

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