当前没有测试数据。

Ex - K-Coloring

分数：$600$ 分

问题描述

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

找到一种在该图的每个顶点上写下一个介于 $1$ 到 $K$ 之间（包括 $1$ 和 $K$），并满足以下条件的写法的个数，对 $998244353$ 取模：

• 相邻的两个顶点上写的数字不相同。

约束条件

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

---

输入

输入从标准输入中给出，格式如下：

$N$ $M$ $K$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_M$ $v_M$

输出

输出在顶点上写下介于 $1$ 到 $K$ 之间（包括 $1$ 和 $K$）的数字的方式的个数，对 $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