Problem Background

The white rabbit likes trees.
The white cloud likes counting.

There are $n$ mice. The white rabbit connects them into a tree with $n - 1$ blue ropes, each connecting two mice. The white cloud connects them into a tree with $n - 1$ red ropes, each also connecting two mice.

The white cloud needs to assign a number to each mouse. This number can be any integer from $[1, y]$.

The white rabbit has a requirement for the white cloud: for any two mice $p, q$, if there exists a path connecting these two mice that belongs to both trees, then $p$ and $q$ must be assigned the same number. A path belonging to both trees means: there exists a sequence $(a_1 = p, a_2, \cdots , a_m = q)$ such that for all $i \in [1, m - 1]$, $a_i$ and $a_{i+1}$ are directly connected by both a red rope and a blue rope.

The white cloud wants to know how many ways there are to assign these numbers.

The mice are struggling and trying to break free from the ropes. Before the white cloud could figure it out, the mice bit through all the red ropes.

The white rabbit was a bit annoyed but still wanted to know the answer. He asked the white cloud: for all possible connections of the red ropes, what is the sum of the number of assignment schemes (i.e., the sum of the number of assignment schemes for all possible red rope connections)?

The mice are still struggling and trying to break free from the ropes. Before the white cloud could figure it out, the mice bit through all the blue ropes as well.

The white rabbit was a bit annoyed but still wanted to know the answer. He asked the white cloud: for all possible connections of both red and blue ropes, what is the sum of the number of assignment schemes (i.e., the sum of the number of assignment schemes for all possible red and blue rope connections)? Two schemes are considered different if and only if there exists at least one pair of mice that are directly connected by different ropes in the two schemes (there are four possibilities for the connection between two mice: no direct connection, only red rope, only blue rope, both red and blue ropes).

The white cloud cried.

Problem Description

This problem contains three questions:
- Question 0: Given the shapes of two trees with $n$ nodes (both trees are labeled from $1$ to $n$), where the first tree is the red tree and the second tree is the blue tree. Assign each node an integer from $[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 a path belonging to both trees is given in the "Problem Background".
- Question 1: Given the blue tree, for all $n^{n-2}$ possible red tree configurations, find the sum of the answers to Question 0.
- Question 2: For all $n^{n-2}$ possible blue tree configurations, find the sum of the answers to Question 1.

Hint: There are $n^{n-2}$ possible trees with $n$ nodes.

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

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

Input Format

The first line contains three integers $n, y, \text{op}$ separated by spaces.
If $\text{op} = 0$, the next $2 \times (n - 1)$ lines describe the blue and red ropes, with the first $(n - 1)$ lines describing the blue ropes and the next $(n - 1)$ lines describing the red ropes.
If $\text{op} = 1$, the next $(n - 1)$ lines describe the blue ropes.
If $\text{op} = 2$, there is no additional input.
Each line describing a rope contains two integers separated by a space, representing the two mice connected by that rope. Mice are numbered from 1.

Output Format

Output a single integer, the answer modulo $998,244,353$.

Sample Input and Output

Input Sample #1

3 2 0
1 2
2 3
1 2
2 3

Output Sample #1

2

Input Sample #2

3 2 1
1 2
2 3

Output Sample #2

10

Input Sample #3

3 2 2

Output Sample #3

30

Notes/Hints

Sample Explanation 1

Both trees are identical, so any two nodes must be assigned the same number, resulting in $2$ schemes.

Sample Explanation 2

There are three possible configurations for the red tree:
1. Contains ropes $(1, 2)$ and $(2, 3)$: Any two mice must be assigned the same number, so the answer to Question 0 is $2$.
2. Contains ropes $(1, 2)$ and $(1, 3)$: 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)$ and $(1, 3)$: Mice $2$ and $3$ must be assigned the same number, so the answer to Question 0 is $2 \times 2 = 4$.

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

Sample Explanation 3

There are three possible configurations for the blue tree. For each configuration of the blue tree, the answer to Question 1 is $10$. Therefore, the answer is $10 \times 3 = 30$.

见题面 Input 部分

见题面 Output 部分