r.i.p
时间限制：1000 ms 内存限制：512 MiB 评测机器较慢，时限改为2000ms
题目描述
老师给了小智一张纸，上面画着一棵有 $n$ 个节点的树。老师还给了小智 $m$ 支彩色笔，每支笔的颜色都是不同的。老师想要让小智用这 $m$ 种颜色给树的节点涂色，使得这棵树满足如下约束：
每个节点都被涂上了这 $m$ 个颜色之一的一种颜色。
相邻两个节点（若存在一条边直接连接 $u$ 和 $v$，则我们称 $u,v$ 相邻）的颜色是不同的。
任何一种颜色被使用的次数都不能超过 $\lfloor\frac{n}{3}\rfloor + 1$。
需要指出的是，虽然每个节点都必须被涂上一种颜色，但是每个颜色并不必须被使用。
如此简单的任务难不倒小智，所以小智提出了一个更困难的问题：他想知道一共有多少种染色的方案满足老师的要求。小智不会解答这个问题，所以来求助你，请你帮他解决他的问题。
因为方案数可能非常大，你只需要输出这个方案数除以 $998244353$ 的余数。两种染色方案不同当且仅当存在一个节点 $u$，使得 $u$ 在两种方案中被染上的颜色不同。
输入格式
第一行是两个整数，依次表示树的节点数 $n$ 和颜色的个数 $m$。
接下来 $(n - 1)$ 行，每行两个整数 $u, v$，表示树上有一条连接 $u, v$ 的边。
输出格式
输出一行一个整数，表示方案数除以 $998244353$ 的余数。
样例
输入 #1
4 4
1 2
1 3
3 4输出 #1
108输入 #2
3 3
1 2
1 3输出 #2
12输入 #3
5 5
1 2
1 3
2 4
3 5输出 #3
1200输入 #4
5 5
1 2
1 3
2 4
2 5输出 #4
1140输入 #5
7 8
1 2
1 3
2 4
2 5
3 6
3 7输出 #5
929376输入 #6
6 6
1 2
1 3
3 4
4 5
3 6输出 #6
18750输入 #7
10 20
1 2
1 3
2 4
2 5
2 6
2 7
3 8
5 9
9 10输出 #7
688946281说明/提示
数据规模与约定
对于全部的测试点，保证 $1 \leq u, v \leq n \leq 120$，$n \leq m \leq 10^6$，保证给出的是一棵树。
| 测试点 | 限制条件 |
|---|---|
| $1\sim 4$ | $n,m\le 8$ |
| $5\sim 7$ | $u=1,\ m\le 100$（星形树） |
| $8\sim 9$ | $u=1$（星形树） |
| $10\sim 13$ | $v=u+1$（链） |
| $14\sim 16$ | $n\le 50$ |
| $17\sim 20$ | $n\le 120$ |
提示
请注意常数因子对程序效率造成的影响。