5017 - [COCI 2017-2018 #2] ​​Usmjeri

给定一颗从 1 到 n 编号的 n 个结点的树。

同时给定m个约束，诸如 (a_i,b_i)。

给每一条边定向，使得每一对约束对存在一条从 a_i 到 b_i 或从 b_i 到 a_i 的路径。

求可行的方案数，答案对 10^9 + 7 取模。

第一行两个数 n,m。

接下来 (n-1) 行，每行两个数，描述树上的一条边。

接下来 m 行，每行两个数 a_i,b_i 描述一对约束 (a_i,b_i)。

输出为一个数，即可行方案数对 10^9 + 1 取模的结果。

对于 100\% 的数据，1 \le n,m \le 5 \times 10^5