Ex - K-Coloring Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

頂点に 1 から N の、辺に 1 から M の番号がついた N 頂点 M 辺の単純無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結んでいます。

このグラフのそれぞれの頂点に 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 以下の整数を書きこむ方法の個数を 998244353 で割った余りを出力せよ。

入力例 1

4 3 2
1 2
2 4
2 3

出力例 1

2

条件を満たす整数の書きこみ方は次の 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

Score : 600 points

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