We are given a tree with nodes denoted with different positive integers from to .
Additionally, you are given node pairs from the tree in the form of .
We need to direct each edge of the tree so that for each given node pair there is a path from to or from to . How many different ways are there to achieve this? Since the solution can be quite large, determine it modulo .
The first line of input contains the positive integers and , the number of nodes in the tree and the number of given node pairs, respectively.
Each of the following lines contains two positive integers, the labels of the nodes connected with an edge.
The of the following lines contains two different positive integers and , the labels of the nodes from the 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 .
In test cases worth 20% of total points, the given tree will be a chain. In other words, node will be connected with an edge to node for all .
In additional test cases worth 40% of total points, it will hold .
Sample Input 1
4 1 1 2 2 3 3 4 2 4
Sample Output 1
Sample Input 2
7 2 1 2 1 3 4 2 2 5 6 5 5 7 1 7 2 6
Sample Output 2
Sample Input 3
4 3 1 2 1 3 1 4 2 3 2 4 3 4
Sample Output 3