Description

本题包含三个问题：

• 问题 0：已知两棵 $n$ 个节点的树的形态（两棵树的节点标号均为 $1$ 至 $n$），其中第一棵树是红树，第二棵树是蓝树。要给予每个节点一个 $[1, y]$ 中的整数，使得对于任意两个节点 $p, q$，如果存在一条路径 $(a_1 = p, a_2, \cdots , a_m = q)$ 同时属于这两棵树，则 $p, q$ 必须被给予相同的数。求给予数的方案数。
  • 存在一条路径同时属于这两棵树的定义见「题目背景」。
• 问题 1：已知蓝树，对于红树的所有 $n^{n-2}$ 种选择方案，求问题 0 的答案之和。
• 问题 2：对于蓝树的所有 $n^{n-2}$ 种选择方案，求问题 1 的答案之和。

提示：$n$ 个节点的树一共有 $n^{n-2}$ 种。

在不同的测试点中，你将可能需要回答不同的问题。我们将用 $\text{op}$ 来指代你需要回答的问题编号（对应上述 0、 1、 2）。

由于答案可能很大，因此你只需要输出答案对 $998, 244, 353$ 取模的结果即可。

Input Format

第一行三个用空格隔开的整数 $n, y, \text{op}$。 如果 $\text{op} = 0$，则接下来 $2 \times (n - 1)$ 行，前 $(n - 1)$ 行每描述一条蓝色绳子，接下来 $(n - 1)$ 行每行描述一条红色绳子。
如果 $\text{op} = 1$，则接下来 $(n - 1)$ 行，每行描述一条蓝色绳子。
如果 $\text{op} = 2$，则接下来没有输入。
描述绳子的各行将包含两个用空格隔开的整数，分别表示被这条绳子连接的两只鼠的编号。鼠的编号是从 $1$ 开始的。

Output Format

输出一个整数，表示答案对 $998, 244, 353$ 取模的结果。

3 2 0
1 2
2 3
1 2
2 3

2

3 2 1
1 2
2 3

10

3 2 2

30

Hint

样例说明 1

两棵树相同，所以任意两个点都必须被给予相同的数，方案数为 $2$。

样例说明 2

红树共有三种可能的情况：

1. 包含绳子 $(1, 2)$（表示连接 $1, 2$ 号鼠的绳子，下同）、$(2, 3)$：此时任意两只鼠都必须被给予相同的数，问题 0 的答案为 $2$。
2. 包含绳子 $(1, 2)$、$(1, 3)$：此时 $1$ 号鼠和 $2$ 号鼠必须被给予相同的数，问题 0 的答案为 $2 \times 2 = 4$。
3. 包含绳子 $(2, 3)$、$(1, 3)$：此时 $2$ 号点和 $3$ 号点必须被给予相同的数，问题 0 的答案为 $2 \times 2 = 4$。

综上，问题 1 的答案为 $2 + 4 + 4 = 10$。

样例说明 3

蓝树一共有三种可能的情况。不难发现，对于蓝树的每一种情况，求得的问题 1 的答案都是 $10$。所以答案为 $10 \times 3 = 30$。

::cute-table{tuack} | 问题类型 $(\mathrm{op})$ | 测试点编号 | $n$ | $y$ | 集训队每点分值 | 非集训队每点分值 | |:---:|:---:|:---:|:---:|:---:|:---:| | 0 | 1 | $\le 10$ | 无特殊限制 | 2 | 18 | | ^ | 2 | $\le 10^{5}$ | ^ | ^ | 5 | | ^ | 3 | ^ | ^ | ^ | ^ | | 1 | 4 | $=3$ | ^ | 1 |4 | | ^ | 5 | $=5$ | ^ | ^ |^ | | ^ | 6 | $\le 500$ | ^ | 6 | ^ | | ^ | 7 | ^ | ^ | ^ | ^ | | ^ | 8 | $\le 5000$ | ^ | ^ |^ | | ^ | 9 | ^ | ^ | ^ |^ | | ^ | 10 | $\le 10^{5}$ | $=1$ | 1 |^ | | ^ | 11 | ^ | 无特殊限制 | 5 | 2 | | ^ | 12 | ^ | ^ | ^ | ^ | | ^ | 13 | ^ | ^ | ^ | ^ | | ^ | 14 | ^ | ^ | ^ | ^ | | 2 | 15 | $=3$ | ^ | 1 | 4 | | ^ | 16 | $=10$ | ^ | ^ | ^ | | ^ | 17 | $\le 500$ | ^ | 6 | ^ | | ^ | 18 | ^ | ^ | ^ | ^ | | ^ | 19 | $\le 5000$ | ^ | ^ | ^ | | ^ | 20 | ^ | ^ | ^ | ^ | | ^ | 21 | $\le 10^{5}$ | $=1$ | 1 | ^ | | ^ | 22 | ^ | 无特殊限制 | 5 | 2 | | ^ | 23 | ^ | ^ | ^ | ^ | | ^ | 24 | ^ | ^ | ^ | ^ | | ^ | 25 | ^ | ^ | ^ | ^ |

为了优化你的阅读体验，我们把测试点编号放在了表格的中间，请注意这一点。

所有测试点均满足 $3 \leq n \leq 10^{5}, 1 \leq y<998244353, o p \in\{0,1,2\}$ 。

洛谷按照集训队分值赋分