In the distant future, physicists have finally discovered the natural laws of time and causality. Even before a person is born, we can use theoretical analysis to know some information about his or her life; in other words, physics allows us to "predict" a person's "destiny" to a certain extent.

Simply put, a person's destiny is a rooted tree $T$ composed of time points: the root node represents birth, and the leaf nodes represent death. Each non-leaf node $u$ has one or more children $v_1, v_2, \dots, v_{c_u}$, representing the $c_u$ different choices that can be made at the time point represented by $u$, which lead to different possibilities. Formally, a choice is an edge $(u, v_i)$ in the tree, where $u$ is the parent of $v_i$.

A person's life is a path from birth (the root node) to death (some leaf node) that does not pass through the same node twice. Any sub-path on this path that contains at least one edge is a "life experience" of this person. All the life experiences that he or she could have by living life in all possible ways are called "potential life experiences." In other words, all potential life experiences are all paths from $u$ to $v$ such that $u, v \in T$, $u \neq v$, and $u$ is an ancestor of $v$. Mathematically, such a potential life experience is denoted as an ordered pair $(u, v)$, and the set of all potential life experiences of tree $T$ is denoted as $P_T$.

Physical theory not only allows us to observe the tree representing destiny but also allows us to analyze whether some potential life experiences are "important." Every choice a person makes—that is, every edge in the tree—can be either important or unimportant. A potential life experience is called important if and only if there is an important edge on its corresponding path. We can observe that some potential life experiences are important: in other words, we can observe a set $Q \subseteq P_T$ such that all potential life experiences $(u, v) \in Q$ are important.

The shape of the tree $T$ has already been calculated and determined, and the set $Q$ has also been observed. The uncertainty of a person's destiny has been greatly reduced. However, the uncertainty is still significant—let's calculate it: for a given tree $T$ and set $Q$, how many different ways are there to determine whether each edge is important, such that the constraints corresponding to the observed $Q$ are satisfied? That is, for any $(u, v) \in Q$, there exists at least one edge on the path from $u$ to $v$ that is determined to be important.

Formally: Given a tree $T = (V, E)$ and a set of pairs $Q \subseteq V \times V$, such that for all $(u, v) \in Q$, $u \neq v$, and $u$ is an ancestor of $v$ in tree $T$. Here $V$ and $E$ represent the set of nodes and the set of edges of tree $T$, respectively. Find the number of different functions $f: E \to \{0, 1\}$ (setting the value $f(e)$ for each edge $e \in E$ to 0 or 1) such that for any $(u, v) \in Q$, there exists an edge $e$ on the path from $u$ to $v$ such that $f(e) = 1$. Since the answer may be very large, you only need to output the result modulo $998, 244, 353$ (a prime number).

Input

• The first line contains a positive integer $n$, representing the size of the tree $T$. The nodes on the tree are numbered from $1$ to $n$, with node $1$ being the root.
• The next $n - 1$ lines each contain two space-separated numbers $x_i, y_i$, satisfying $1 \le x_i, y_i \le n$, representing an edge between nodes $x_i$ and $y_i$ in the tree. The direction of this edge is not guaranteed.
• The next line contains a non-negative integer $m$, representing the number of pieces of observed information.
• The next $m$ lines each contain two space-separated numbers $u_i, v_i$, representing $(u_i, v_i) \in Q$. Note: The input data may contain duplicate information; in other words, there may exist $i \neq j$ such that $u_i = u_j$ and $v_i = v_j$.

Output

• Output a single integer representing the number of ways modulo $998, 244, 353$.

Examples

Input 1

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

Output 1

10

Note 1

There are 16 possible schemes in total. The 6 schemes that do not satisfy the requirements are: $(1, 2), (2, 3), (3, 5)$ determined as unimportant, $(3, 4)$ determined as important: No constraints in set $Q$ are satisfied. $(1, 2), (2, 3), (3, 4), (3, 5)$ determined as unimportant: No constraints in set $Q$ are satisfied. $(1, 2), (2, 3)$ determined as unimportant, $(3, 4), (3, 5)$ determined as important: $(1, 3)$ in set $Q$ is not satisfied. $(1, 2), (2, 3), (3, 4)$ determined as unimportant, $(3, 5)$ determined as important: $(1, 3)$ in set $Q$ is not satisfied. $(2, 3), (3, 5)$ determined as unimportant, $(1, 2), (3, 4)$ determined as important: $(2, 5)$ in set $Q$ is not satisfied. $(2, 3), (3, 4), (3, 5)$ determined as unimportant, $(1, 2)$ determined as important: $(2, 5)$ in set $Q$ is not satisfied. * In all other schemes, the constraints in set $Q$ are all satisfied.

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

Output 2

960

Examples 3

See destiny/destiny3.in and destiny/destiny3.ans in the contestant directory.

Examples 4

See destiny/destiny4.in and destiny/destiny4.ans in the contestant directory.

Constraints

All data satisfies: $n \le 5 \times 10^5$, $m \le 5 \times 10^5$. The input forms a tree, and for $1 \le i \le m$, $u_i$ is always an ancestor of $v_i$.

Complete Binary Tree: In this problem, a tree where every non-leaf node has both left and right children, and all leaf nodes have the same depth, is called a full binary tree. A tree formed by taking the first few nodes of a full binary tree, when nodes are numbered from top to bottom and left to right, is called a complete binary tree.