{"raw_statement":[{"iden":"background","content":"请注意：**本题不是树链剖分模板题**。"},{"iden":"statement","content":"给定一棵 $n$ 个节点的树 $T$ 以及树上的 $m$ 条 **不同的** 路径 $I_i = (u_i, v_i)(u_i\\neq v_i)$。具体地，$I_i$ 表示树上 $u_i$ 和 $v_i$ 之间的简单路径上所有点形成的点集。\n\n考虑 $T$ 上某条路径 $I = (u, v)$，定义 $f(I) = \\sum\\limits_{i = 1} ^ m\\sum\\limits_{j = 1} ^ m [I_i\\cup I = I_j\\cup I]$。\n\n对于 $T$ 上所有不同路径 $I$，求 $f(I)$ 之和，并将答案对 $998244353$ 取模。也就是说，你需要求 $\\left(\\sum\\limits_{u = 1} ^ n\\sum\\limits_{v = u} ^ n f((u, v))\\right) \\bmod 998244353$。"},{"iden":"input","content":"第一行一个整数 $S$，表示子任务编号。样例的子任务编号为 $-1$。\n\n第二行两个整数 $n, m$，分别表示树的大小和路径条数。\n\n接下来 $n - 1$ 行，每行两个整数 $x_i, y_i$ 表示 $T$ 上的一条边。\n\n接下来 $m$ 行，每行两个整数 $u_i, v_i$ 表示第 $i$ 条路径 $I_i$。\n\n**保证给定路径两两不同**。"},{"iden":"output","content":"输出一行一个整数表示答案。"},{"iden":"note","content":"本题采用捆绑测试，共 $25$ 个子任务，分别编号为 $0\\sim 24$。**注意评测子任务编号为实际子任务编号 $+1$**。\n\n子任务编号模 $5$ 的余数将子任务按数据大小划分。\n\n- 若子任务编号模 $5$ 余 $0$，则 $n, m\\leq 100$，记为 A1。\n- 若子任务编号模 $5$ 余 $1$，则 $n, m\\leq 500$，记为 B1。依赖于 A1。\n- 若子任务编号模 $5$ 余 $2$，则 $n, m\\leq 1557$，记为 C1。依赖于 B1。\n- 若子任务编号模 $5$ 余 $3$，则 $n, m\\leq 85500$，记为 D1。依赖于 C1。\n- 若子任务编号模 $5$ 余 $4$，则 $n, m\\leq 2\\times 10 ^ 5$，记为 E1。依赖于 D1。\n\n子任务编号除以 $5$ 的商将子任务按特殊限制划分。\n\n- 若子任务编号除以 $5$ 商 $0$，则 $T$ 是一条链，记为 A2。\n- 若子任务编号除以 $5$ 商 $1$，则 $T$ 是一个菊花，记为 B2。\n- 若子任务编号除以 $5$ 商 $2$，则所有路径端点互不相同，记为 C2。\n- 若子任务编号除以 $5$ 商 $3$，则所有路径以同一点为一端，记为 D2。\n- 若子任务编号除以 $5$ 商 $4$，则无特殊限制，记为 E2。依赖于 A2，B2，C2，D2。\n\n对于 $100\\%$ 的数据，$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$，且所有 $(x_i, y_i)$ 形成一棵树，所有 $I_i = (u_i, v_i)$ 互不相同，$u_i\\neq v_i$。\n\n各子任务分值如下表所示。\n\n| **得分** | **A1** | **B1** | **C1** | **D1** | **E1** | **总和** |\n| :------: | :----: | :----: | :----: | :----: | :----: | :------: |\n|  **A2**  |  $1$   |  $2$   |  $3$   |  $7$   |  $7$   |   $20$   |\n|  **B2**  |  $1$   |  $2$   |  $3$   |  $4$   |  $4$   |   $14$   |\n|  **C2**  |  $1$   |  $2$   |  $5$   |  $7$   |  $7$   |   $22$   |\n|  **D2**  |  $1$   |  $3$   |  $5$   |  $4$   |  $5$   |   $18$   |\n|  **E2**  |  $2$   |  $3$   |  $3$   |  $9$   |  $9$   |   $26$   |\n| **总和** |  $6$   |  $12$  |  $19$  |  $31$  |  $32$  |  $100$   |\n\n**注：洛谷评测无子任务依赖**。\n\n来源：2022 年集训队互测 Round 4。\n\n出题人：Alex_Wei。"}],"translated_statement":null,"sample_group":[["-1\n3 3\n1 2\n2 3\n1 2\n2 3\n1 3","32"],["-1\n4 6\n1 2\n1 3\n1 4\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4","120"],["-1\n7 7\n1 2\n1 3\n2 4\n4 5\n5 6\n5 7\n5 7\n3 1\n4 7\n7 1\n2 6\n3 6\n3 5","330"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}