配点 : $500$ 点

問題文

$N$ 頂点 $M$ 辺の単純無向グラフが与えられます。頂点は $1, \dots, N$ と番号付けられ、$i \, (1 \leq i \leq M)$ 番目の辺は頂点 $U_i, V_i$ を結んでいます。

それぞれの頂点を赤または青で塗る方法は全部で $2^N$ 通りあります。これらのうち、以下の条件を全て満たすものの総数を $998244353$ で割った余りを求めてください。

• 赤く塗られた頂点がちょうど $K$ 個ある
• 異なる色で塗られた頂点を結ぶ辺の本数は偶数である

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $0 \leq K \leq N$
• $1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)$
• $(U_i, V_i) \neq (U_j, V_j) \, (i \neq j)$
• 入力は全て整数

入力

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

$N$ $M$ $K$

$U_1$ $V_1$

$\vdots$

$U_M$ $V_M$

出力

答えを出力せよ。

4 4 2
1 2
1 3
2 3
3 4

2

以下の $2$ 通りが条件を満たします。

• 頂点 $1, 2$ を赤く、頂点 $3, 4$ を青く塗る。
• 頂点 $3, 4$ を赤く、頂点 $1, 2$ を青く塗る。

上記の塗り方について、異なる色で塗られた頂点を結ぶ辺は $2$ 番目の辺と $3$ 番目の辺です。

10 10 3
1 2
2 4
1 5
3 6
3 9
4 10
7 8
9 10
5 9
3 4

64