25072번 - Destiny 다국어

문제

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円$.

입력

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$.

출력

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

제한

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$.

힌트