간선 방향 정하기

시간 제한2초메모리 제한256 MB

요약

트리의 각 간선을 방향을 정해, 주어진 모든 정점 쌍 사이에 한 방향으로든 경로가 존재하도록 하는 경우의 수를 10^9+7로 나눈 나머지로 구한다.

난이도: 어려움10점 중 8점
유형: 트리, DFS, 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

노드 $N$ 개로 이루어진 트리가 주어진다. 각 노드에는 $1$ 부터 $N$ 까지 서로 다른 번호가 붙어 있다. 여기에 더해 트리의 노드 쌍 $M$ 개 $(a_1, b_1), (a_2, b_2), \dots, (a_M, b_M)$ 이 주어진다.

트리의 간선마다 방향을 하나씩 정하려고 한다. 주어진 노드 쌍 $(a_i, b_i)$ 마다 $a_i$ 에서 $b_i$ 로 가는 경로가 있거나 $b_i$ 에서 $a_i$ 로 가는 경로가 있어야 한다. 이런 방향 배정이 모두 몇 가지인지 구하라. 답이 매우 클 수 있으므로 $10^9 + 7$ 로 나눈 나머지를 구한다.

트리는 노드 $N$ 개와 간선 $N - 1$ 개로 이루어진 그래프이며, 어느 노드에서 다른 어느 노드로도 경로가 있다.

입력

첫째 줄에 트리의 노드 수 $N$ 과 주어지는 노드 쌍의 수 $M$ 이 주어진다 ( $1 \le N, M \le 3 \times 10^5$ ).

다음 $N - 1$ 개 줄에는 간선으로 이어진 두 노드의 번호가 주어진다.

그다음 $M$ 개 줄 중 $i$ 번째 줄에는 $i$ 번째 노드 쌍을 이루는 서로 다른 두 양의 정수 $a_i$ 와 $b_i$ 가 주어진다. 노드 쌍은 모두 서로 다르다.

출력

조건을 만족하도록 트리의 간선에 방향을 정하는 경우의 수를 $10^9 + 7$ 로 나눈 나머지를 한 줄에 출력한다.

예제3

예제 1
입력
```
4 1
1 2
2 3
3 4
2 4
```
예상 출력
```
4
```
예제 2
입력
```
7 2
1 2
1 3
4 2
2 5
6 5
5 7
1 7
2 6
```
예상 출력
```
8
```
예제 3
입력
```
4 3
1 2
1 3
1 4
2 3
2 4
3 4
```
예상 출력
```
0
```