102947: [Atcoder]ABC294 Ex - K-Coloring

Problem Statement

You are given a simple undirected graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ connects vertex $u_i$ and vertex $v_i$.

Find the number, modulo $998244353$, of ways to write an integer between $1$ and $K$, inclusive, on each vertex of this graph to satisfy the following condition:

• two vertices connected by an edge always have different numbers written on them.

Constraints

• $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$
• The given graph is simple.

Input

The input is given from Standard Input in the following format:

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

Output

Print the number, modulo $998244353$, of ways to write integers between $1$ and $K$, inclusive, on the vertices to satisfy the condition.

Sample Input 1

4 3 2
1 2
2 4
2 3

Sample Output 1

2

Here are the two ways to satisfy the condition.

• Write $1$ on vertices $1, 3, 4$, and write $2$ on vertex $2$.
• Write $1$ on vertex $2$, and write $2$ on vertex $1, 3, 4$.

Sample Input 2

4 0 10

Sample Output 2

10000

All $10^4$ ways satisfy the condition.

Sample Input 3

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

Sample Output 3

120

Sample Input 4

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

Sample Output 4

838338733

Sample Input 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

Sample Output 5

418104233

问题描述

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

找到满足以下条件的在每个顶点上写一个1到K（包括1和K）之间的整数的方法的数量，取模数为998244353：

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

约束条件

• 1≤N≤30
• 0≤M≤min(30,N(N-1)/2)
• 1≤K≤10^9
• 1≤u_i＜v_i≤N
• 给定的图是简单的。

输入

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

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

输出

打印出满足条件的在顶点上写整数的方法的数量，取模数为998244353。

样例输入1

4 3 2
1 2
2 4
2 3

样例输出1

2

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

• 在顶点1、3、4上写1，在顶点2上写2。
• 在顶点2上写1，在顶点1、3、4上写2。

样例输入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