Background

Chuanzhi Cup 2021 Finals Problem G.

Problem Description

A teacher at Chuanzhi Specialization Academy assigned Xiaozhi a task.

The teacher gave Xiaozhi a sheet of paper with a tree of $n$ nodes drawn on it (if you do not know what a tree is, you can refer to the explanation in the previous problem). The teacher also gave Xiaozhi $m$ colored pens, each with a different color. The teacher wants Xiaozhi to color the nodes of the tree using these $m$ colors, so that the tree satisfies the following constraints:

1. Each node is colored with exactly one of the $m$ colors.
2. Any two adjacent nodes (if there is an edge directly connecting $u$ and $v$, then we say $u$ and $v$ are adjacent) have different colors.
3. The number of times any single color is used cannot exceed $\lfloor\frac{n}{3}\rfloor + 1$.

Note that although every node must be colored with some color, not every color has to be used.

This simple task is not difficult for Xiaozhi, so he raised a harder question: he wants to know how many coloring schemes satisfy the teacher's requirements. Xiaozhi cannot solve this, so he asks you for help. Please solve this problem for him.

Because the number of schemes may be very large, you only need to output the remainder when this number is divided by $998,244,353$. Two coloring schemes are 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 in the tree $n$ and the number of colors $m$, respectively.
The next $(n - 1)$ lines each contain two integers $u, v$, indicating that there is an edge connecting $u$ and $v$ in the tree.

Output Format

Output one line with one integer, representing the remainder of the number of schemes modulo $998,244,353$.

4 4
1 2
1 3
3 4

108

3 3
1 2
1 3

12

5 5
1 2
1 3
2 4
3 5

1200

5 5
1 2
1 3
2 4
2 5

1140

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

929376

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

18750

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

688946281

Hint

Constraints

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

Hint

Please pay attention to the impact of constant factors on program efficiency.

Translated by ChatGPT 5