← 返回题目列表

AtCoder · abc294_h

Ex. K-着色

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给你一个简单的无向图 N 顶点编号 1 to N 和 M 边编号 1 to M。边缘 i 连接顶点 u_i 和顶点 v_i.

求模数 998244353,在之间写入整数的方法 1 和 K,包含在内,在此图的每个顶点上满足以下条件:

  • 由一条边连接的两个顶点总是写有不同的数字。

约束

  • 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

输出

打印数字,模数 998244353,在之间写入整数的方法 1 和 K,包含在内,在满足条件的顶点上。


示例输入 1

4 3 2
1 2
2 4
2 3

示例输出 1

2

以下是满足条件的两种方法。

  • 写 顶点上的 1 在顶点上 1, 3, 4,并写入 2 在顶点 2.
  • 写 顶点上的 1 在顶点 2,并写入 2 在顶点 1, 3, 4.

示例输入 2

4 0 10

示例输出 2

10000

全部 10^4 方式满足条件。


示例输入 3

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

示例输出 3

120

示例输入 4

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

示例输出 4

838338733

示例输入 5

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

示例输出 5

418104233