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

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

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

给每一条边定向,使得每一对约束对存在一条从 a_ib_i 或从 b_ia_i 的路径。

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

输入

第一行两个数 n,m

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

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

输出

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

样例

输入

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

提示

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

时间限制 3 秒
内存限制 250 MB
讨论 统计
上一题 下一题