/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 頂点 M 辺の単純無向グラフが与えられます。頂点は 1, \dots, N と番号付けられ、i \, (1 \leq i \leq M) 番目の辺は頂点 U_i, V_i を結んでいます。
それぞれの頂点を赤または青で塗る方法は全部で 2^N 通りあります。これらのうち、以下の条件を全て満たすものの総数を 998244353 で割った余りを求めてください。
- 赤く塗られた頂点がちょうど K 個ある
- 異なる色で塗られた頂点を結ぶ辺の本数は偶数である
制約
- 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)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K U_1 V_1 \vdots U_M V_M
出力
答えを出力せよ。
入力例 1
4 4 2 1 2 1 3 2 3 3 4
出力例 1
2
以下の 2 通りが条件を満たします。
- 頂点 1, 2 を赤く、頂点 3, 4 を青く塗る。
- 頂点 3, 4 を赤く、頂点 1, 2 を青く塗る。
上記の塗り方について、異なる色で塗られた頂点を結ぶ辺は 2 番目の辺と 3 番目の辺です。
入力例 2
10 10 3 1 2 2 4 1 5 3 6 3 9 4 10 7 8 9 10 5 9 3 4
出力例 2
64
Score : 500 points
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