$1s512MB(unnmei.in/out)$

这 $n$ 位少女的命运由 $n$ 条羁绊深深联系在一起，第 $i$ 条羁绊是属于 $a_i$ 和 $b_i$ 之间的。

若两位少女 $a,b$ 间存在一条羁绊，那么称他俩互为挚友。

但是在不同的世界线里，这 $n$ 条羁绊不一定同时存在，甚至这 $n$ 位少女也不一定同时存在。但唯一知道的是，在所有平行世界里，存在的少女都能通过羁绊关系连通起来。（也就是连通子图）

而对于某一个平行世界 $S$ ，令 $x(S)$ 为这个世界里有小于等于 $1$ 个挚友的少女数量，$y(S)$ 为这个世界里有大于 $1$ 个挚友的少女数量，那么这个世界的稳定值为： $$ k^{x(S)}\times (1-k)^{n-x(s)-y(S)}\times (x(s)+y(s)) $$ 其中 $k$ 是命定之数，在任何平行世界里都不会发生改变。

现在请求出所有平行世界的稳定值之和，对 $998244353$ 取余。

输入格式

第一行两个整数 $n,k$ 。

接下来 $n$ 行，每行两个整数 $a_i,b_i$ ，表示 $a_i$ 和 $b_i$ 间有一条羁绊。

保证无重边自环且 $n$ 位少女通过羁绊关系能够联通。

输出格式

一行一个整数表示答案。

样例

样例 1 输入

4 2
1 2
2 3
3 1
3 4

样例 1 输出

33

样例 1 解释

选择第 $1、3$ 条边构成的子图，$x(S)=2,y(S)=1,f(S)=2^2\times (1-2)^{4-2-1}\times (2+1)=-12$。

选择第 $1、2、3$ 条边构成的子图，$x(S)=0,y(S)=3,f(S)=2^0\times (1-2)^{4-0-3}\times (0+3)=-3$。

选择由顶点 $1$ 构成的子图，$x(S)=1,y(S)=0,f(S)=2^1\times (1-2)^{4-1-0}\times (1+0)=-2$。

注意，只有一个顶点也算连通子图

样例 2 输入

4 6
1 2
2 3
3 1
3 4

样例 2 输出

2661

样例 3 输入

13 4
1 2
3 5
3 2
11 10
9 1
4 1
1 3
12 4
6 5
8 2
5 7
4 13
10 1

样例 3 输出

973949412

数据范围

保证对于所有数据满足 $3\leq n\leq 10^5,2\leq k\leq 6,1\leq a_i,b_i\leq n$ 。

• down