시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 10 6 5 55.556%

문제

We are given a tree1 with N nodes denoted with different positive integers from 1 to N. Additionally, you are given M node pairs from the tree in the form of (a1, b1), (a2, b2), …, (aM, bM).

We need to direct each edge of the tree so that for each given node pair (ai, bi) there is a path from ai to bi or from bi to ai. How many different ways are there to achieve this? Since the solution can be quite large, determine it modulo 109 + 7.

1A tree is a graph that consists of N nodes and N - 1 edges such that there exists a path from each node to each other node.

입력

The first line of input contains the positive integers N and M (1 ≤ N, M ≤ 3·105), the number of nodes in the tree and the number of given node pairs, respectively.

Each of the following N - 1 lines contains two positive integers, the labels of the nodes connected with an edge.

The i th of the following M lines contains two different positive integers ai and bi , the labels of the nodes from the i th node pair. All node pairs will be mutually different.

출력

You must output a single line containing the total number of different ways to direct the edges of the tree that meet the requirement from the task, modulo 109 + 7.

예제 입력 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