题目描述

我们有一颗从$\red{1}$到$\red{n}$编号的$\red{n}$个结点的树，此外，您将从树中获得$\red{M}$个节点对，形式为$\red{(a1,b1),(a2,b2),}$$\red{…（am,bm).}$

我们需要给每一条边定向，使得每一对节点对存在一条从$\red{ai}$到$\red{bi}$或从$\red{bi}$到$\red{ai}$的路径。

现在要求方案数，对$\red{10^9+7}$取$\red{mod}$即可。

输入格式

第一行输入两个正整数$\red{n，}$$\red{m}$。

接下来$\red{n}$行，每行$\red{m}$个字符描述地图。

输出格式

第一行两个整数,$\red{n,m}$

接下来$\red{n-1}$行，每一行两个整数，描述一条树边。

接下来$\red{m}$行，描述$\red{ai，}$$\red{bi}$

样例

输入样例1

4 1

1 2

2 3

3 4

2 4

输出样例1

4

输入样例2

7 2

1 2

1 3

4 2

2 5

6 5

5 7

1 7

2 6

输出样例2

8

输入样例3

4 3

1 2

1 3

1 4

2 3

2 4

3 4

输出样例3

0

提示

数据范围

对于前$\red{20\%}$的数据，保证是一条链。

另有$\red{40\%}$的数据，$\red{n，}$$\red{m<=5000}$

对于$\red{100\%}$的数据，$\red{n，}$$\red{m<=300000}$