Problem Background

Chuanzhi Cup 2021 Finals Problem G.

Problem Description

The teacher at Chuanzhi Specialized Training Institute has assigned a task to Xiaozhi.

The teacher provided Xiaozhi with a sheet of paper depicting a tree with $n$ nodes (if you are unfamiliar with trees, refer to the explanation in the previous problem). The teacher also gave Xiaozhi $m$ colored pens, each with a distinct color. The teacher wants Xiaozhi to color the nodes of the tree with these $m$ colors, ensuring the following constraints are met:

1. Each node is colored with one of the $m$ colors.
2. Adjacent nodes (if there is an edge directly connecting $u$ and $v$, we say $u$ and $v$ are adjacent) have different colors.
3. No color is used more than $\lfloor\frac{n}{3}\rfloor + 1$ times.

It should be noted that although each node must be colored, not every color must be used.

This simple task is not challenging for Xiaozhi, so he posed a more difficult question: he wants to know how many coloring schemes satisfy the teacher's requirements. Xiaozhi cannot solve this problem, so he seeks your help. Please help him solve his problem.

Since the number of schemes can be very large, you only need to output the remainder of this number divided by $998,244,353$. Two coloring schemes are considered different if and only if there exists a node $u$ such that the color of $u$ is different in the two schemes.

Input Format

The first line contains two integers, representing the number of nodes $n$ in the tree and the number of colors $m$, respectively.
The next $(n - 1)$ lines each contain two integers $u$ and $v$, indicating an edge connecting nodes $u$ and $v$ in the tree.

Output Format

Output a single integer, which is the remainder of the number of schemes divided by $998,244,353$.

Sample Input and Output

Sample Input #1

4 4
1 2
1 3
3 4

Sample Output #1

108

Sample Input #2

3 3
1 2
1 3

Sample Output #2

12

Sample Input #3

5 5
1 2
1 3
2 4
3 5

Sample Output #3

1200

Sample Input #4

5 5
1 2
1 3
2 4
2 5

Sample Output #4

1140

Sample Input #5

7 8
1 2
1 3
2 4
2 5
3 6
3 7

Sample Output #5

929376

Sample Input #6

6 6
1 2
1 3
3 4
4 5
3 6

Sample Output #6

18750

Sample Input #7

10 20
1 2
1 3
2 4
2 5
2 6
2 7
3 8
5 9
9 10

Sample Output #7

688946281

Notes

Data Size and Constraints

For all test cases, it is guaranteed that $1 \leq u, v \leq n \leq 100$, $n \leq m \leq 10^6$, and the input represents a tree.

Hints

Please be aware of the impact of constant factors on program efficiency.

见题面 Input 部分

见题面 Output 部分