题目描述

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

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

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

输入格式

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

$N$ $M$ $K$ $U_1$ $V_1$ $\vdots$ $U_M$ $V_M$

输出格式

答えを出力せよ。

题目大意

给出一个 $N$ 个点、$M$ 条边的简单无向图，每个点可以染成红色或蓝色，所有点必须染色。求满足以下要求的染色方案数：

• 有 $K$ 个点染成红色

• 两端颜色不同的边数为偶数

答案对 $998244353$ 取模。

输入的第一行是 $N,M,K$；之后 $M$ 行，每行两个整数 $U_i,V_i$，表示一条边连接的两个结点。

输出满足要求的方案数对 $998244353$ 取模的结果。

• $2\le N\le 2\times 10^5$
• $1\le M\le 2\times 10^5$
• $0\le K\le N$
• 对于 $1\le i\le N$，$1\le U_i\lt V_i \le N$
• 对于 $i\neq j$，$(U_i,V_i)\neq(U_j,V_j)$
• 输入的数据均为整数。

4 4 2
1 2
1 3
2 3
3 4

2

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

64

提示

制約

• $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)$
• 入力は全て整数

Sample Explanation 1

以下の $2$ 通りが条件を満たします。 - 頂点 $1,\ 2$ を赤く、頂点 $3,\ 4$ を青く塗る。 - 頂点 $3,\ 4$ を赤く、頂点 $1,\ 2$ を青く塗る。 上記の塗り方について、異なる色で塗られた頂点を結ぶ辺は $2$ 番目の辺と $3$ 番目の辺です。