分数: 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