15326번 - Usmjeri 다국어

We are given a tree¹ 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 (a₁, b₁), (a₂, b₂), …, (a_M, b_M).

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

¹A 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·10⁵), 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 10⁹ + 7.