โชคชะตา: นับวิธีระบายเส้น ให้ทุกเส้นทางที่กำหนดมีจุดตัดอย่างน้อยหนึ่งจุด

// NOI 2020 "Destiny" / โชคชะตา (programming.in.th 2042)
// เต็มขอบเขต: N, M <= 500,000  เวลา O((N + M) log N)
//
// dp[v][j] = จำนวนวิธีระบายเส้นในกิ่งของ v ที่ข้อบังคับในกิ่งปิดครบ
//            และข้อที่ยังค้าง ข้อที่ u ลึกที่สุดอยู่ที่ความลึก j (j = 0 คือไม่มีอะไรค้าง)
// ช่อง j = 0 เก็บเป็นตัวแปร s[v] ส่วนช่อง j >= 1 เก็บในเซกเมนต์ทรีที่ควบรวมได้ (แกนคือความลึก)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;

// ---------- อ่านอินพุต ----------
static char buf[1 << 25];
int bufLen = 0, bufPos = 0;
inline int readChar() {
    if (bufPos == bufLen) { bufLen = (int)fread(buf, 1, sizeof(buf), stdin); bufPos = 0; if (bufLen <= 0) return -1; }
    return buf[bufPos++];
}
inline int readInt() {
    int c = readChar();
    while (c != -1 && (c < '0' || c > '9')) c = readChar();
    int x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = readChar(); }
    return x;
}

// ---------- เซกเมนต์ทรีที่ควบรวมได้ ----------
// ปมเก็บผลรวมของช่วง กับป้ายคูณที่ยังไม่ส่งลงลูก (lazy tag)
// ปมที่ถูกทิ้งตอนควบรวมเข้ากองว่าง freeList แล้วเอากลับมาใช้ใหม่
vector<int> lc, rc;
vector<ll> sm, mul;
vector<int> freeList;
int newNode() {
    int x;
    if (!freeList.empty()) { x = freeList.back(); freeList.pop_back(); }
    else { x = (int)lc.size(); lc.push_back(0); rc.push_back(0); sm.push_back(0); mul.push_back(1); }
    lc[x] = rc[x] = 0; sm[x] = 0; mul[x] = 1;
    return x;
}
void freeNode(int x) { freeList.push_back(x); }
inline void applyMul(int x, ll k) { if (x) { sm[x] = sm[x] * k % MOD; mul[x] = mul[x] * k % MOD; } }
inline void push(int x) {
    if (mul[x] != 1) { applyMul(lc[x], mul[x]); applyMul(rc[x], mul[x]); mul[x] = 1; }
}
inline void pull(int x) { sm[x] = ((lc[x] ? sm[lc[x]] : 0) + (rc[x] ? sm[rc[x]] : 0)) % MOD; }

// บวก val ที่ช่อง pos
int addAt(int x, int l, int r, int pos, ll val) {
    if (!x) x = newNode();
    if (l == r) { sm[x] = (sm[x] + val) % MOD; return x; }
    push(x);
    int m = (l + r) / 2;
    if (pos <= m) lc[x] = addAt(lc[x], l, m, pos, val);
    else rc[x] = addAt(rc[x], m + 1, r, pos, val);
    pull(x);
    return x;
}
// ลบช่วง [ql, qr] ทิ้ง คืนผลรวมของสิ่งที่ลบผ่าน taken
int cutRange(int x, int l, int r, int ql, int qr, ll &taken) {
    if (!x || qr < l || r < ql) return x;
    if (ql <= l && r <= qr) {
        // ทิ้งทั้งต้นย่อย คืนแค่ปมบนสุดเข้ากองว่าง ปมลูกหลานไม่มีใครชี้ถึงแล้วจึงไม่เป็นปัญหา
        taken = (taken + sm[x]) % MOD;
        freeNode(x);
        return 0;
    }
    push(x);
    int m = (l + r) / 2;
    lc[x] = cutRange(lc[x], l, m, ql, qr, taken);
    rc[x] = cutRange(rc[x], m + 1, r, ql, qr, taken);
    if (!lc[x] && !rc[x]) { freeNode(x); return 0; }
    pull(x);
    return x;
}
// รวมสองตาราง C[j] = A[j] * preB[j] + B[j] * preA[j-1]
// pa = ผลรวมของ A ทุกช่องก่อน l, pb = ผลรวมของ B ทุกช่องก่อน l (รวมช่อง 0 ที่อยู่นอกต้นไม้)
int mergeTree(int a, int b, int l, int r, ll pa, ll pb) {
    if (!a && !b) return 0;
    if (!b) { applyMul(a, pb); return a; }          // B ว่างทั้งช่วง preB คงที่เท่ากับ pb
    if (!a) { applyMul(b, pa); return b; }          // A ว่างทั้งช่วง preA คงที่เท่ากับ pa
    if (l == r) {
        ll A = sm[a], B = sm[b];
        sm[a] = (A * ((pb + B) % MOD) + B * pa) % MOD;
        freeNode(b);
        return a;
    }
    push(a); push(b);
    int m = (l + r) / 2;
    ll aL = lc[a] ? sm[lc[a]] : 0, bL = lc[b] ? sm[lc[b]] : 0;
    lc[a] = mergeTree(lc[a], lc[b], l, m, pa, pb);
    rc[a] = mergeTree(rc[a], rc[b], m + 1, r, (pa + aL) % MOD, (pb + bL) % MOD);
    freeNode(b);
    pull(a);
    return a;
}

int main() {
    int n = readInt();
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) { int x = readInt(), y = readInt(); adj[x].push_back(y); adj[y].push_back(x); }

    // ---------- ปักรากที่ 1 หาความลึกกับลำดับ ----------
    // ใช้ BFS เพราะต้นไม้ลึกได้ถึงห้าแสน การเรียกตัวเองซ้ำจะทำสแต็กล้น
    vector<int> par(n + 1, 0), dep(n + 1, 0), order;
    order.reserve(n);
    dep[1] = 1; order.push_back(1);
    for (size_t i = 0; i < order.size(); i++) {
        int v = order[i];
        for (int w : adj[v]) if (w != par[v]) { par[w] = v; dep[w] = dep[v] + 1; order.push_back(w); }
    }
    int maxDep = 1;
    for (int v = 1; v <= n; v++) maxDep = max(maxDep, dep[v]);

    // ---------- ข้อบังคับ: เก็บแค่ u ที่ลึกที่สุดต่อจุดปลาย ----------
    int m = readInt();
    vector<int> att(n + 1, 0);
    for (int i = 0; i < m; i++) { int u = readInt(), v = readInt(); att[v] = max(att[v], dep[u]); }

    // ---------- ไล่จากใบขึ้นหาราก ----------
    lc.reserve(1 << 22); rc.reserve(1 << 22); sm.reserve(1 << 22); mul.reserve(1 << 22);
    newNode();                               // ปม 0 คือ "ว่าง" ห้ามใช้
    vector<ll> s(n + 1, 1);                  // ช่อง j = 0 ของแต่ละจุด เริ่มที่ 1 (ยังไม่มีเส้นให้ระบาย)
    vector<int> root(n + 1, 0);              // ต้นไม้ของช่อง j >= 1
    const int L = 1, R = max(1, maxDep);
    for (int i = n - 1; i >= 0; i--) {
        int v = order[i];
        // แขวนข้อบังคับที่จบที่ v: ทุกช่องที่ j < b ถูกกวาดมาเทลงช่อง b
        int b = att[v];
        if (b >= 1) {
            ll acc = s[v];
            s[v] = 0;
            if (b - 1 >= 1) root[v] = cutRange(root[v], L, R, 1, b - 1, acc);
            root[v] = addAt(root[v], L, R, b, acc);
        }
        if (v == 1) break;
        // ส่งขึ้นไปให้พ่อ p ผ่านเส้น (p, v) ให้ D = ความลึกของพ่อ
        int p = par[v], D = dep[p];
        ll dead = 0;
        root[v] = cutRange(root[v], L, R, D, D, dead);    // ช่อง D: ระบาย 0 แล้วตาย (u คือพ่อพอดี)
        ll S = (s[v] + (root[v] ? sm[root[v]] : 0) + dead) % MOD;  // ทางระบาย 1 รับทั้งตารางเดิม
        ll g0 = (s[v] + S) % MOD;                          // ช่อง 0: ระบาย 0 ตอนไม่มีอะไรค้าง + ระบาย 1
        // รวมเข้ากับตารางของพ่อ (A = พ่อ, B = g)
        ll A0 = s[p];
        root[p] = mergeTree(root[p], root[v], L, R, A0, g0);
        s[p] = A0 * g0 % MOD;
        root[v] = 0;
    }
    printf("%lld\n", s[1] % MOD);
    return 0;
}

// NOI 2020 "Destiny" / โชคชะตา (programming.in.th 2042) - ตารางเต็ม
// สูตรของเฉลยตอนที่ 3 เขียนตรง ๆ ตารางของจุดที่ลึก d ยาว d ช่อง
// เวลาเป็นสัดส่วนกับผลรวมความลึกของทุกจุด: ชนะชุด N <= 2,000 และชุดต้นไม้ไบนารีสมบูรณ์ (ลึกราว log N)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) { int x, y; if (scanf("%d %d", &x, &y) != 2) return 0; adj[x].push_back(y); adj[y].push_back(x); }
    vector<int> par(n + 1, 0), dep(n + 1, 0), order;
    dep[1] = 1; order.push_back(1);
    for (size_t i = 0; i < order.size(); i++) {
        int v = order[i];
        for (int w : adj[v]) if (w != par[v]) { par[w] = v; dep[w] = dep[v] + 1; order.push_back(w); }
    }
    int m;
    if (scanf("%d", &m) != 1) return 0;
    vector<int> att(n + 1, 0);
    for (int i = 0; i < m; i++) { int u, v; if (scanf("%d %d", &u, &v) != 2) return 0; att[v] = max(att[v], dep[u]); }

    // cur[v] คือตารางของ v ระหว่างที่ลูกทยอยรวมเข้ามา ยาว dep[v] ช่อง (j = 0 ถึง dep[v] - 1)
    // สร้างตอนต้องใช้ครั้งแรก และทิ้งทันทีที่ส่งขึ้นไปหาพ่อแล้ว ถ้าสร้างล่วงหน้าทุกจุด
    // ต้นไม้เส้นตรงแสนจุดจะกินห้าพันล้านช่องพร้อมกัน
    vector<vector<ll>> cur(n + 1);
    auto ensure = [&](int v) { if (cur[v].empty()) { cur[v].assign(dep[v], 0); cur[v][0] = 1; } };
    for (int i = n - 1; i >= 0; i--) {
        int v = order[i];
        ensure(v);
        vector<ll> &d = cur[v];
        // แขวนข้อบังคับที่จบที่ v
        int b = att[v];
        if (b >= 1) {
            ll acc = 0;
            for (int j = 0; j < b; j++) { acc = (acc + d[j]) % MOD; d[j] = 0; }
            d[b] = (d[b] + acc) % MOD;
        }
        if (v == 1) break;
        // ขอบ (p, v): ช่อง 0 รับ dp[0] + S, ช่อง 1..D-1 รับตรง ๆ, ช่อง D ตาย
        int p = par[v], D = dep[p];
        ll S = 0;
        for (ll x : d) S = (S + x) % MOD;
        vector<ll> g(D, 0);
        g[0] = (d[0] + S) % MOD;
        for (int j = 1; j < D; j++) g[j] = d[j];
        // รวมแบบเอาค่ามากสุด: C[j] = A[j] * preB[j] + B[j] * preA[j-1]
        ensure(p);
        vector<ll> &A = cur[p];
        ll pa = 0, pb = 0;
        for (int j = 0; j < D; j++) {
            ll pbj = (pb + g[j]) % MOD;
            ll c = (A[j] * pbj + pa * g[j]) % MOD;
            pa = (pa + A[j]) % MOD;
            pb = pbj;
            A[j] = c;
        }
        vector<ll>().swap(d);
    }
    ll ans = 0;
    for (ll x : cur[1]) ans = (ans + x) % MOD;
    printf("%lld\n", ans);
    return 0;
}

// NOI 2020 "Destiny" / โชคชะตา (programming.in.th 2042) - ตัวตรวจ
// ไล่ทุกการระบาย 2^(N-1) แบบ แล้วเดินวิถีของทุกคู่ตามนิยามในโจทย์ตรง ๆ
// ไม่ใช้ความลึก ไม่มีสถานะ ไม่ยุบข้อบังคับ ใช้ได้กับชุด N <= 10 และเป็นตัวเทียบตอน stress test
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        if (scanf("%d %d", &x, &y) != 2) return 0;
        adj[x].push_back({y, i});
        adj[y].push_back({x, i});
    }
    // พ่อและเลขเส้นที่ต่อขึ้นไปหาพ่อ
    vector<int> par(n + 1, 0), pe(n + 1, -1), st = {1};
    vector<bool> seen(n + 1, false);
    seen[1] = true;
    while (!st.empty()) {
        int v = st.back(); st.pop_back();
        for (auto [w, e] : adj[v]) if (!seen[w]) { seen[w] = true; par[w] = v; pe[w] = e; st.push_back(w); }
    }
    int m;
    if (scanf("%d", &m) != 1) return 0;
    vector<long long> need(m, 0);   // มาสก์ของเส้นบนวิถีของแต่ละคู่
    for (int i = 0; i < m; i++) {
        int u, v;
        if (scanf("%d %d", &u, &v) != 2) return 0;
        for (int x = v; x != u; x = par[x]) need[i] |= 1LL << pe[x];
    }
    long long cnt = 0;
    for (long long mask = 0; mask < (1LL << (n - 1)); mask++) {
        bool ok = true;
        for (int i = 0; i < m && ok; i++) if (!(mask & need[i])) ok = false;
        if (ok) cnt++;
    }
    printf("%lld\n", cnt % 998244353);
    return 0;
}