该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Stain

时间限制：$1s$

空间限制：$256MB$

题目描述

给定一个 $N$ 个点、 $M$ 条边的简单无向图，每个点需要染成黑色或白色。给出有 $K$ 个点染成黑色且两端颜色不同的边的数量为偶数的染色方案数。答案对 $998244353$ 取模。

数据格式

输入

第一行包含整数 $N,M,K$。

接下来的 $M$ 行，每行包含两个整数 $u,v$，表示无向边。

输出

输出 $1$ 行，给出满足要求的方案数对 $998244353$ 取模的结果。

样例

输入1

5 5 2
1 2
3 4
2 3
4 5
1 3

输出1

4

输入2

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

输出2

112

数据范围及约定

$2\ \leq\ N\ \leq\ 2\times\ 10^5$ $ N-1\ \leq\ M\ \leq\ \min(\frac{N(N-1)}{2},2\times\ 10^5) $ $0\ \leq\ K\ \leq\ N$