Score : $500$ points

问题陈述

给定一个包含 $N$ 个顶点和 $M$ 条边的简单无向图。顶点编号为 $1, \dots, N$，其中第 $i$-条 $(1 \leq i \leq M)$ 边连接顶点 $U_i$ 和 $V_i$。

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

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

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1, \dots, N$, and the $i$-th $(1 \leq i \leq M)$ edge connects Vertices $U_i$ and $V_i$.

There are $2^N$ ways to paint each vertex red or blue. Find the number, modulo $998244353$, of such ways that satisfy all of the following conditions:

• There are exactly $K$ vertices painted red.
• There is an even number of edges connecting vertices painted in different colors.

Constraints

• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$ $K$

$U_1$ $V_1$

$\vdots$

$U_M$ $V_M$

Output

Print the answer.

Sample Input 1

4 4 2
1 2
1 3
2 3
3 4

Sample Output 1

2

The following two ways satisfy the conditions.

• Paint Vertices $1$ and $2$ red and Vertices $3$ and $4$ blue.
• Paint Vertices $3$ and $4$ red and Vertices $1$ and $2$ blue.

In either of the ways above, the $2$-nd and $3$-rd edges connect vertices painted in different colors.

Sample Input 2

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

Sample Output 2

64

update @ 2024/3/10 11:06:14