AT_abc262_e [ABC262E] Red and Blue Graph

给定一个有 $N$ 个顶点、$M$ 条边的简单无向图。顶点编号为 $1, 2, \dots, N$，第 $i$ 条边连接顶点 $U_i$ 和 $V_i$。 将每个顶点涂成红色或蓝色的方法共有 $2^N$ 种。在这些方法中，满足以下所有条件的方法数，模 $998244353$ 后的余数是多少？ - 恰好有 $K$ 个顶点被涂成红色。 - 连接颜色不同顶点的边的数量为偶数。

输入以如下格式从标准输入给出。 > $N$ $M$ $K$ > $U_1$ $V_1$ > $\vdots$ > $U_M$ $V_M$

输出答案。

## 限制条件 - $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 < V_i \leq N \quad (1 \leq i \leq M)$ - $(U_i, V_i) \neq (U_j, V_j) \quad (i \neq j)$ - 输入均为整数 ## 样例解释 1 以下 $2$ 种方案满足条件： - 将顶点 $1, 2$ 涂成红色，顶点 $3, 4$ 涂成蓝色。 - 将顶点 $3, 4$ 涂成红色，顶点 $1, 2$ 涂成蓝色。 对于上述涂色方法，连接颜色不同顶点的边是第 $2$ 条和第 $3$ 条边。 由 ChatGPT 4.1 翻译