当前没有测试数据。

E - 红色和蓝色的图

得分：500分

题目描述

给定一个简单无向图，有$N$个顶点和$M$条边。顶点编号为$1, \dots, N$，第$i$条边（$1≤i≤M$）连接着顶点$U_i$和$V_i$。

有$2^N$种方式将每个顶点涂成红色或蓝色。求满足以下条件的方式的数量（模$998244353$）：

• 恰好有$K$个顶点涂成红色。
• 连接不同颜色的顶点的边数为偶数。

约束条件

• $2 ≤ N ≤ 2 × 10^5$
• $1 ≤ M ≤ 2 × 10^5$
• $0 ≤ K ≤ N$
• $1 ≤ U_i < V_i ≤ N \, (1 ≤ i ≤ M)$
• $(U_i, V_i) ≠ (U_j, V_j) \, (i ≠ 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

满足条件的方式有两种。

• 将顶点$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