Score : $600$ points

## 问题描述

给定一个包含 $N$ 个顶点（编号从 $1$ 到 $N$）的简单无向图，以及 $M$ 条边（编号从 $1$ 到 $M$）。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

要求计算满足以下条件的不同整数标记方式的数量，结果对 $998244353$ 取模：

-   通过一条边相连的两个顶点上所写的数字始终不相同。

请注意，这里的“在每个顶点上写一个整数”范围是从 $1$ 到 $K$（包含 $1$ 和 $K$）。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 12:15:20