题目描述

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

このグラフのそれぞれの頂点に $1$ 以上 $K$ 以下の整数を書きこむ方法のうち、次の条件を満たす方法の個数を $998244353$ で割った余りを求めてください。

• 辺で結ばれた頂点同士には異なる数が書きこまれている。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

条件を満たすように頂点に $1$ 以上 $K$ 以下の整数を書きこむ方法の個数を $998244353$ で割った余りを出力せよ。

题目大意

zjh 有一个有 $n$ 个顶点、$m$ 条边的简单无向图。

求出有多少种填数方案使得，在这个图的每个顶点中填入一个 $1$ 到 $k$ 之间的整数之后每条边所连的两个点上的数都不同。你只需要输出方案数对 $998244353$ 取模的值。

Translated by

4 3 2
1 2
2 4
2 3

2

4 0 10

10000

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

120

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

838338733

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

418104233

提示

制約

• $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$
• 入力で与えられるグラフは単純

Sample Explanation 1

条件を満たす整数の書きこみ方は次の $2$ 通りです。 - 頂点 $1,\ 3,\ 4$ に $1$ を、頂点 $2$ に $2$ を書きこむ。 - 頂点 $2$ に $1$ を、頂点 $1,\ 3,\ 4$ に $2$ を書きこむ。

Sample Explanation 2

$10^4$ 通り全ての書きこみ方が条件を満たします。