K 染色

题目描述

给定一个简单无向图，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

求在图的每个顶点上写一个 $1$ 到 $K$ 之间的整数，使得满足以下条件的方案数，对 $998244353$ 取模：

被一条边连接的两个顶点上写的数字一定不同。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$ $K$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

输出格式

输出满足条件的方案数对 $998244353$ 取模后的值。

样例

4 3 2
1 2
2 4
2 3

2

满足条件的方案有以下两种。

在顶点 $1, 3, 4$ 上写 $1$，在顶点 $2$ 上写 $2$。

在顶点 $2$ 上写 $1$，在顶点 $1, 3, 4$ 上写 $2$。

4 0 10

10000

全部 $10^4$ 种方案都满足条件。

5 10 5
3 5
1 3
1 2
1 4
3 4
2 5
4 5
1 5
2 3
2 4

120

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

838338733

7 12 1000000000
4 5
2 7
3 4
6 7
3 5
5 6
5 7
1 3
4 7
1 5
2 3
3 6

418104233

数据范围

• $1 \le N \le 30$
• $0 \le M \le \min \left(30, \frac{N(N-1)}{2} \right)$
• $1 \le K \le 10^9$
• $1 \le u_i \lt v_i \le N$
• 给定的图是简单图