Description

This problem contains three questions:

• Question 0: The shapes of two trees with $n$ nodes are given (both trees have nodes labeled from $1$ to $n$). The first tree is the red tree, and the second tree is the blue tree. You need to assign each node an integer in $[1, y]$ such that for any two nodes $p, q$, if there exists a path $(a_1 = p, a_2, \cdots , a_m = q)$ that belongs to both trees, then $p, q$ must be assigned the same number. Find the number of assignment schemes.
  • The definition of “there exists a path that belongs to both trees” is the same as in the “Background”.
• Question 1: The blue tree is given. For all $n^{n-2}$ choices of the red tree, compute the sum of the answers to Question 0.
• Question 2: For all $n^{n-2}$ choices of the blue tree, compute the sum of the answers to Question 1.

Hint: There are $n^{n-2}$ different trees on $n$ nodes.

In different test points, you may need to answer different questions. We use $\text{op}$ to denote the index of the question you need to answer (corresponding to 0, 1, 2 above).

Since the answer may be very large, you only need to output it modulo $998, 244, 353$.

Input Format

The first line contains three integers $n, y, \text{op}$ separated by spaces.
If $\text{op} = 0$, then the next $2 \times (n - 1)$ lines follow: the first $(n - 1)$ lines each describe a blue rope, and the next $(n - 1)$ lines each describe a red rope.
If $\text{op} = 1$, then the next $(n - 1)$ lines follow, each describing a blue rope.
If $\text{op} = 2$, then there is no further input.
Each rope description line contains two integers separated by a space, representing the indices of the two mice connected by this rope. The mice are numbered starting from $1$.

Output Format

Output one integer, representing the answer modulo $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

Sample Explanation 1

The two trees are the same, so any two nodes must be assigned the same number. The number of schemes is $2$.

Sample Explanation 2

There are three possible red trees:

1. Contains ropes $(1, 2)$ (meaning the rope connecting mice $1$ and $2$, similarly below), $(2, 3)$. Then any two mice must be assigned the same number, so the answer to Question 0 is $2$.
2. Contains ropes $(1, 2)$, $(1, 3)$. Then mice $1$ and $2$ must be assigned the same number, so the answer to Question 0 is $2 \times 2 = 4$.
3. Contains ropes $(2, 3)$, $(1, 3)$. Then node $2$ and node $3$ must be assigned the same number, so the answer to Question 0 is $2 \times 2 = 4$.

Therefore, the answer to Question 1 is $2 + 4 + 4 = 10$.

Sample Explanation 3

There are three possible blue trees. It is not hard to see that for each blue tree, the computed answer to Question 1 is $10$. So the answer is $10 \times 3 = 30$.

::cute-table{tuack}

To optimize your reading experience, we placed the Test Point ID in the middle of the table; please pay attention to this.

All test points satisfy $3 \leq n \leq 10^{5}, 1 \leq y<998244353, o p \in\{0,1,2\}$.

Luogu scores according to CTT points

Translated by ChatGPT 5