P4434 [COCI 2017/2018 #2] ​​Usmjeri

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

### 数据规模与约定 * 对于 $20\%$ 的数据，满足树是一条链，即 $\forall i