Подсказка: в последнем абзаце условия приведено краткое формальное описание задачи.

В далёком будущем физики наконец открыли законы природы, управляющие временем и причинностью. Даже до рождения человека теоретический анализ позволяет узнать некоторые сведения о его или её жизни. Иными словами, физика позволяет в некоторой степени «предсказывать» «судьбу» человека.

Проще говоря, судьба человека — это корневое дерево $T$, состоящее из моментов времени: корень дерева обозначает рождение, а листья — смерть. Каждая нелистовая вершина $u$ имеет одного или нескольких детей $v_1,v_2,\ldots,v_{c_u}$, которые представляют различные возможности, к которым могут привести $c_u$ различных решений человека в момент времени, соответствующий $u$. Формально выбор — это ребро дерева $(u,v_i)$, где $u$ является родителем $v_i$.

Жизнь человека — это путь без повторяющихся вершин от рождения (корня) до смерти (какого-либо листа). Любой подпуть этого пути, содержащий хотя бы одно ребро, является эпизодом жизни этого человека. Все эпизоды, которые он или она может пережить, проживая жизнь всеми возможными способами, называются потенциальными эпизодами жизни. Иными словами, это все пути из $u$ в $v$, где $u,v\in T$, $u\ne v$ и $u$ — предок $v$. Математически такой потенциальный эпизод обозначается упорядоченной парой $(u,v)$, а множество всех потенциальных эпизодов жизни дерева $T$ обозначается $P_T$.

Физическая теория позволяет не только наблюдать дерево судьбы, но и анализировать, являются ли некоторые потенциальные эпизоды жизни «важными». Каждый выбор человека — то есть каждое ребро дерева — может быть важным или неважным. Потенциальный эпизод жизни называется важным тогда и только тогда, когда на соответствующем пути есть важное ребро. Мы можем наблюдать, что некоторые потенциальные эпизоды важны. Иными словами, наблюдения дают множество $Q\subseteq P_T$, все потенциальные эпизоды $(u,v)\in Q$ которого важны.

Структура дерева $T$ уже вычислена, а множество $Q$ уже получено наблюдениями, поэтому неопределённость судьбы человека существенно уменьшилась. Но она всё ещё огромна. Давайте посчитаем: для заданных дерева $T$ и множества $Q$ сколько существует различных способов определить важность каждого ребра так, чтобы выполнялись ограничения, соответствующие наблюдаемому множеству $Q$? То есть для любой пары $(u,v)\in Q$ хотя бы одно ребро на пути из $u$ в $v$ должно быть объявлено важным.

Формально: даны дерево $T=(V,E)$ и множество пар вершин $Q\subseteq V\times V$, причём для всех $(u,v)\in Q$ выполнено $u\ne v$, и $u$ является предком $v$ в дереве $T$. Здесь $V$ и $E$ обозначают соответственно множества вершин и рёбер дерева $T$. Найдите количество различных функций $f:E\to\{0,1\}$ (каждому ребру $e\in E$ присваивается значение $f(e)$, равное $0$ или $1$), таких что для любой пары $(u,v)\in Q$ на пути из $u$ в $v$ есть ребро $e$ с $f(e)=1$. Ответ может быть очень большим, поэтому выведите его остаток по модулю $998\,244\,353$ (это простое число).

Входные данные

Данные считываются из файла destiny.in.

• Первая строка содержит положительное целое число $n$ — размер дерева $T$. Вершины пронумерованы от $1$ до $n$, корнем является вершина $1$.
• Следующие $n-1$ строк содержат по два числа $x_i,y_i$, разделённых пробелом, где $1\le x_i,y_i\le n$. Они обозначают ребро между вершинами $x_i$ и $y_i$; направление этого ребра не гарантируется.
• Следующая строка содержит неотрицательное целое число $m$ — количество полученных наблюдений.
• Следующие $m$ строк содержат по два числа $u_i,v_i$, разделённых пробелом, которые означают $(u_i,v_i)\in Q$. Обратите внимание: входные данные могут содержать повторяющиеся сведения; иначе говоря, могут существовать $i\ne j$, для которых $u_i=u_j$ и $v_i=v_j$.

Размеры входных данных и ограничения приведены в таблице в конце условия.

Выходные данные

Ответ выводится в файл destiny.out.

• Выведите единственное целое число в одной строке — количество способов по модулю $998\,244\,353$.

Примеры

Входные данные 1

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

Выходные данные 1

10

Примечание

Всего существует $16$ способов. Следующие $6$ не удовлетворяют условию:

• $(1,2),(2,3),(3,5)$ объявлены неважными, а $(3,4)$ — важным: ни одно ограничение множества $Q$ не выполнено.
• $(1,2),(2,3),(3,4),(3,5)$ объявлены неважными: ни одно ограничение множества $Q$ не выполнено.
• $(1,2),(2,3)$ объявлены неважными, а $(3,4),(3,5)$ — важными: ограничение $(1,3)$ из $Q$ не выполнено.
• $(1,2),(2,3),(3,4)$ объявлены неважными, а $(3,5)$ — важным: ограничение $(1,3)$ из $Q$ не выполнено.
• $(2,3),(3,5)$ объявлены неважными, а $(1,2),(3,4)$ — важными: ограничение $(2,5)$ из $Q$ не выполнено.
• $(2,3),(3,4),(3,5)$ объявлены неважными, а $(1,2)$ — важным: ограничение $(2,5)$ из $Q$ не выполнено.
• Во всех остальных случаях все ограничения множества $Q$ выполнены.

Входные данные 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

Выходные данные 2

960

Пример 3

См. файлы destiny/destiny3.in и destiny/destiny3.ans в каталоге участника.

Пример 4

См. файлы destiny/destiny4.in и destiny/destiny4.ans в каталоге участника.

Ограничения

Для всех данных: $n\le 5\times 10^5$, $m\le 5\times 10^5$. Входные данные задают дерево, и для $1\le i\le m$ вершина $u_i$ всегда является предком $v_i$.

Полное двоичное дерево: в этой задаче дерево, у которого каждая нелистовая вершина имеет левого и правого ребёнка, а все листья находятся на одинаковой глубине, называется совершенным двоичным деревом. Если пронумеровать вершины совершенного двоичного дерева сверху вниз и слева направо, то дерево, образованное некоторым количеством вершин с наименьшими номерами, называется полным двоичным деревом.