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

У далекому майбутньому фізики нарешті відкрили природні закони часу та причинності. Навіть до народження людини за допомогою теоретичного аналізу можна дізнатися деякі відомості про її життя. Іншими словами, фізика дозволяє нам певною мірою «передбачати» «долю» людини.

Якщо говорити просто, доля людини — це кореневе дерево $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\}$ (які надають значенню $f(e)$ кожного ребра $e \in 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$.

Повне бінарне дерево: у цій задачі дерево, в якому кожна нелистова вершина має ліву й праву дочірні вершини, а всі листки мають однакову глибину, називається ідеальним бінарним деревом. Якщо пронумерувати вершини ідеального бінарного дерева зверху вниз і зліва направо, то дерево, утворене деякою кількістю вершин із найменшими номерами, називається повним бінарним деревом.