Background

Please note: This problem is not a heavy-light decomposition template problem.

Problem Description

You are given a tree $T$ with $n$ nodes and $m$ distinct paths on the tree $I_i = (u_i, v_i)(u_i\neq v_i)$. Specifically, $I_i$ represents the set of all nodes on the simple path between $u_i$ and $v_i$ on the tree.

Consider a path on $T$, $I = (u, v)$. Define $f(I) = \sum\limits_{i = 1} ^ m\sum\limits_{j = 1} ^ m [I_i\cup I = I_j\cup I]$.

For all distinct paths $I$ on $T$, find the sum of $f(I)$, and take the answer modulo $998244353$. That is, you need to compute $\left(\sum\limits_{u = 1} ^ n\sum\limits_{v = u} ^ n f((u, v))\right) \bmod 998244353$.

Input Format

The first line contains an integer $S$, indicating the subtask ID. In the sample, the subtask ID is $-1$.

The second line contains two integers $n, m$, representing the size of the tree and the number of paths.

The next $n - 1$ lines each contain two integers $x_i, y_i$, representing an edge of $T$.

The next $m$ lines each contain two integers $u_i, v_i$, representing the $i$-th path $I_i$.

It is guaranteed that all given paths are pairwise distinct.

Output Format

Output one line with one integer, the answer.

-1
3 3
1 2
2 3
1 2
2 3
1 3

32

-1
4 6
1 2
1 3
1 4
1 2
1 3
1 4
2 3
2 4
3 4

120

-1
7 7
1 2
1 3
2 4
4 5
5 6
5 7
5 7
3 1
4 7
7 1
2 6
3 6
3 5

330

Hint

This problem uses bundled testdata, with a total of $25$ subtasks, numbered $0\sim 24$. Note that the evaluated subtask ID equals the actual subtask ID $+1$.

The remainder of the subtask ID modulo $5$ classifies subtasks by data size.

• If the subtask ID modulo $5$ is $0$, then $n, m\leq 100$, denoted as A1.
• If the subtask ID modulo $5$ is $1$, then $n, m\leq 500$, denoted as B1. Depends on A1.
• If the subtask ID modulo $5$ is $2$, then $n, m\leq 1557$, denoted as C1. Depends on B1.
• If the subtask ID modulo $5$ is $3$, then $n, m\leq 85500$, denoted as D1. Depends on C1.
• If the subtask ID modulo $5$ is $4$, then $n, m\leq 2\times 10 ^ 5$, denoted as E1. Depends on D1.

The quotient of the subtask ID divided by $5$ classifies subtasks by special constraints.

• If the quotient is $0$, then $T$ is a chain, denoted as A2.
• If the quotient is $1$, then $T$ is a star, denoted as B2.
• If the quotient is $2$, then all path endpoints are pairwise distinct, denoted as C2.
• If the quotient is $3$, then all paths share one common endpoint, denoted as D2.
• If the quotient is $4$, then there are no special constraints, denoted as E2. Depends on A2, B2, C2, D2.

Constraints

For $100\%$ of the data, $2\leq n\leq 2\times 10 ^ 5$, $1\leq m\leq \min(\frac {n(n - 1)} 2, 2\times 10 ^ 5)$, $1\leq u_i, v_i, x_i, y_i\leq n$, and all $(x_i, y_i)$ form a tree, all $I_i = (u_i, v_i)$ are pairwise distinct, and $u_i\neq v_i$.

The scores of each subtask are shown in the following table.

Note: Luogu evaluation has no subtask dependencies.

Source: 2022 CTT Mutual Test Round 4.

Problem setter: Alex_Wei.

Translated by ChatGPT 5