AT_abc262_e [ABC262E] Red and Blue Graph

[problemUrl]: https://atcoder.jp/contests/abc262/tasks/abc262_e $ 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 $

答えを出力せよ。

### 制約 - $ 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) $ - 入力は全て整数 ### Sample Explanation 1 以下の $ 2 $ 通りが条件を満たします。 - 頂点 $ 1,\ 2 $ を赤く、頂点 $ 3,\ 4 $ を青く塗る。 - 頂点 $ 3,\ 4 $ を赤く、頂点 $ 1,\ 2 $ を青く塗る。 上記の塗り方について、異なる色で塗られた頂点を結ぶ辺は $ 2 $ 番目の辺と $ 3 $ 番目の辺です。