Given a tree ~T = (V,E)~ (~V~ is the set of vertices and ~E~ is the set of edges) and a set of pairs of vertices ~Q \subset V \times V~ satisfying for all ~(u,v) \in Q~, ~u \ne v~ and ~u~ is an ancestor of ~v~ on tree ~T~, you are supposed to compute how many functions ~f: E \to \{0, 1\}~ (i.e. for each edge ~e \in E~, the value of ~f(e)~ would be either ~0~ or ~1~) satisfies the condition for any ~(u,v) \in Q~ there exists an edge ~e~ on the path from ~u~ to ~v~ such that ~f(e) = 1~. Output the answer modulo ~998\,244\,353~.

Input Specification

The first line contains an input ~n~ denoting the number of vertices in tree ~T~. The nodes are numbered from 1 to ~n~ and the root node is node 1. In the following ~n-1~ lines, each line contains two integers separated by a space ~x_i, y_i~ such that ~1 \le x_i,y_i \le n~ denoting there exists an edge on the tree between node ~x_i~ and ~y_i~. There are no guarantees for the direction of the edge. The following line contains an integer ~m~ denoting the size of ~Q~. In the following ~m~ lines, each line contains two integers separated by a space ~u_i,v_i~ denoting ~(u_i,v_i) \in Q~. There may be duplication, or in other words, there might exist some ~i \ne j~ such that ~u_i = u_j~ and ~v_i = v_j~.

Output Specification

The output contains only an integer denoting the number of functions ~f~ satisfying the condition above.

Sample Input 1

5
1 2
2 3
3 4
3 5
2
1 3
2 5

Sample Output 1

10

Sample Input 2

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

960

Constraints

For all test cases, ~n \le 5 \times 10^5~, ~m \le 5 \times 10^5~.
The input forms a tree, where for all ~1 \le i \le m~, ~u_i~ is the ancestor of ~v_i~.

Test Case	~n~	~m~	Additional Constraints
1	~\le 10~	~\le 10~	None.
2
3
4
5	~\le 500~	~\le 15~
6	~\le 10\,000~	~\le 10~
7	~\le 100\,000~	~\le 16~
8	~\le 500\,000~
9	~\le 100\,000~	~\le 22~
10	~\le 500\,000~
11	~\le 600~	~\le 600~
12	~\le 1000~	~\le 1000~
13	~\le 2000~	~\le 500\,000~
14
15	~\le 500\,000~	~\le 2000~
16
17	~\le 100\,000~	~\le 100\,000~	See below.
18
19	~\le 50\,000~		None.
20	~\le 80\,000~
21	~\le 100\,000~	~\le 500\,000~
22
23	~\le 500\,000~
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.