红色与蓝色图

题目描述

给定一个具有 $N$ 个顶点和 $M$ 条边的简单无向图。顶点编号为 $1, \dots, N$，第 $i$ 条边 $(1 \le i \le M)$ 连接顶点 $U_i$ 和顶点 $V_i$。

将每个顶点染成红色或蓝色共有 $2^N$ 种方式。求满足以下所有条件的染色方式的数量，答案对 $998244353$ 取模：

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

输入格式

输入按以下格式从标准输入给出：

$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

数据范围

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