레이팅 미적용We are given a tree with \(N\) nodes denoted with different positive integers from 1 to \(N\).
1
Additionally, you are given \(M\) node pairs from the tree in the form of (a_{1}, b_{1}), (a_{2}, b_{2}), ..., (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^{9} + 7\).
In test cases worth 20% of total points, the given tree will be a chain. In other words, node \(i\)
will be connected with an edge to node \(i + 1\) for all \(i < N\).
In additional test cases worth 40% of total points, it will hold N, \(M \le 5 \cdot 10^{3}\).
The first line of input contains the positive integers \(N\) and \(M\) (\(1 \le N\), \(M \le 3 \cdot 10^{5}\)), 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 \(a_{i}\) and \(b_{i}\), 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^{9} + 7\).
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