Given a tree
(
is the set of vertices and
is the set
of edges) and a set of pairs of vertices
satisfying for all
,
and
is an ancestor of
on tree
, you are supposed to compute how many functions
(i.e. for each edge
, the value of
would be either
or
) satisfies the condition for any
there exists an edge
on the path from
to
such
that
. Output the answer modulo
.
Input Specification
The first line contains an input
denoting the number of
vertices in tree
. The nodes are numbered from 1 to
and the root
node is node 1. In the following
lines, each line contains two
integers separated by a space
such that
denoting there exists an edge on the tree
between node
and
. There are no guarantees for the direction
of the edge. The following line contains an integer
denoting the
size of
. In the following
lines, each line contains two integers
separated by a space
denoting
. There may be
duplication, or in other words, there might exist some
such
that
and
.
Output Specification
The output contains only an integer denoting the number of
functions
satisfying the condition above.
Sample Input 1
Copy
5
1 2
2 3
3 4
3 5
2
1 3
2 5
Sample Output 1
Copy
10
Sample Input 2
Copy
15
2 1
3 1
4 3
5 2
6 3
7 6
8 4
9 5
10 7
11 5
12 10
13 3
14 9
15 8
6
3 12
5 11
2 5
3 13
8 15
1 13
Sample Output 2
Copy
960
Constraints
For all test cases,
,
.
The input forms a tree, where for all
,
is the ancestor of
.
Test Case |  |  | Additional Constraints |
1 |  |  | None. |
2 |
3 |
4 |
5 |  |  |
6 |  |  |
7 |  |  |
8 |  |
9 |  |  |
10 |  |
11 |  |  |
12 |  |  |
13 |  |  |
14 |
15 |  |  |
16 |
17 |  |  | See below. |
18 |
19 |  | None. |
20 |  |
21 |  |  |
22 |
23 |  |
24 |
25 |
In this problem, a perfect binary tree is a binary tree such that each
non-leaf node has two children and the depths of all leaf nodes are the
same; if we number the nodes in a perfect binary tree from up to down,
from left to right, the tree formed by the nodes with smallest numbers
form a complete binary tree. Test cases 17 and 18 are complete binary
trees.
Comments