Red and Blue Graph

题目描述

你被给定了一个具有 $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$

输出格式

输出答案。

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)$ 输入中的所有值均为整数。以下两种方式满足条件。

将顶点 $1$ 和 $2$ 涂成红色，顶点 $3$ 和 $4$ 涂成蓝色。 将顶点 $3$ 和 $4$ 涂成红色，顶点 $1$ 和 $2$ 涂成蓝色。

在上述任一方式中，第 $2$ 条和第 $3$ 条边连接的都是颜色不同的顶点。

标签: AtCoder|abc262E

来源

AtCoder|abc262E