Fate of a Lifetime

In the distant future, physicists have uncovered the natural laws of time and causality. Even before a person is born, it is possible to theoretically "predict" some aspects of their destiny. In this problem, a person’s fate is modeled as a rooted tree \(T=(V,E)\) where the root represents birth and each leaf represents death. Every non‐leaf node \(u\) has one or more children \(v_1,v_2,\dots,v_{c_u}\) corresponding to the different choices available at time point \(u\). A life is simply a path from the root to some leaf and every subpath (with at least one edge) is considered a distinct "life experience."

Formally, every potential life experience is an ordered pair \((u,v)\) (with \(u\) an ancestor of \(v\) in \(T\)). Let \(\mathcal P_T\) be the set of all such pairs.

Physical theory also allows us to decide which decisions (edges in \(T\)) are "important." A life experience (i.e. a pair \((u,v)\)) is said to be important if and only if some edge on the unique path from \(u\) to \(v\) is marked as important. We are given a set \(\mathcal Q\subseteq \mathcal P_T\) of important life experiences.

Your task is: Given the tree \(T\) and the set \(\mathcal Q\) (where each \((u,v)\in \mathcal Q\) satisfies that \(u\) is an ancestor of \(v\) and \(u\neq v\)), count the number of functions \(f:E\to \{0,1\}\) (i.e. assignments of 0/1 to every edge) such that for every \((u,v)\in \(\mathcal Q\) there exists at least one edge \(e\) on the unique path from \(u\) to \(v\) with \(f(e)=1\). Since the answer might be huge, output it modulo 998244353.

Formal Statement:

Given a tree \(T=(V,E)\) and a set of pairs \(\mathcal Q\subseteq V\times V\) such that for every \((u,v)\in \mathcal Q\), \(u\) is an ancestor of \(v\) in \(T\). Count the number of functions \(f:E\to \{0,1\}\) satisfying: for each \((u,v)\in \mathcal Q\), there exists an edge \(e\) on the unique path from \(u\) to \(v\) with \(f(e)=1\). Output the result modulo \(998244353\).

inputFormat

The input begins with an integer n (the number of nodes). The next n-1 lines each contain two integers u and v representing an edge between nodes u and v in the tree \(T\) (the tree is undirected; you may assume that node 1 is the root).

The next line contains an integer q representing the number of queries (i.e. important life experiences observed). Each of the following q lines contains two integers u and v (with u \neq v and u is an ancestor of v) representing a pair in \(\mathcal Q\).

outputFormat

Output a single integer — the number of functions \(f:E\to \{0,1\}\) that satisfy the conditions, modulo 998244353.

sample

3
1 2
1 3
1
1 2

2