[省选联考 2023] 城市建造

题目描述

在这个国度里面有 $n$ 座城市,一开始城市之间修有若干条双向道路,导致这些城市形成了 $t \ge 2$ 个连通块,特别的,这些连通块之间两两大小差的绝对值不超过 $0 \le k \le 1$。为了方便城市建设与发展,$n$ 座城市中的某 $t$ 座城市**在这 $t$ 座城市之间**额外修建了至少一条双向道路,使得所有城市连通。 现在已经知道额外修建后的所有道路,你需要算出有哪些双向道路集合 $E'$,满足这些道路有可能是后来额外修建的,请输出答案对 $998,244,353$ 取模的结果。 即给定一张 $n$ 个点 $m$ 条边的**无向连通**图 $G = (V, E)$,询问有多少该图的子图 $G' = (V', E')$,满足 $E' \ne \varnothing$ 且 $G - E'$ 中恰好有 $|V'|$ 个连通块,且任意两个连通块大小之差不超过 $k$,保证 $0 \le k \le 1$,请输出答案对 $998,244,353$ 取模的结果。

输入输出格式

输入格式


输入的第一行包含三个正整数 $n, m, k$,分别表示城市数、修建后的道路数以及任意两个连通块大小之差的上限。 接下来 $m$ 行每行包含两个正整数 $u, v$,表示城市 $u$ 和 $v$ 之间存在一条双向道路,保证 $u \ne v$。

输出格式


输出一个数表示答案对 $998,244,353$ 取模后的结果。

输入输出样例

输入样例 #1

4 4 1
1 2
2 3
1 3
3 4

输出样例 #1

2

输入样例 #2

见附件中的 cities/cities2.in

输出样例 #2

见附件中的 cities/cities2.ans

输入样例 #3

见附件中的 cities/cities3.in

输出样例 #3

见附件中的 cities/cities3.ans

输入样例 #4

见附件中的 cities/cities4.in

输出样例 #4

见附件中的 cities/cities4.ans

说明

**【样例 1 解释】** 有以下两种情况: - 本来只有 $(3, 4)$ 这一条道路,此时有三个连通块,分别为 $\{1\}, \{2\}, \{3, 4\}$;后来城市 $1, 2, 3$ 决定在它们三座城市中额外修建了 $(1, 2), (2, 3), (1, 3)$ 这三条道路,使得所有城市连通。 - 本来没有任何道路,此时有四个连通块,分别为 $\{1\}, \{2\}, \{3\}, \{4\}$;后来城市 $1, 2, 3, 4$ 决定在它们四座城市中额外修建了 $(1, 2), (2, 3), (1, 3), (3, 4)$ 这四条道路,使得所有城市连通。 **【数据范围】** 对于所有的数据,保证:$3 \le n \le 10^5$,$n - 1 \le m \le 2 \times 10^5$,$0 \le k \le 1$。 |测试点|$n$|$m$|$k$| |:-:|:-:|:-:|:-:| |1, 2|$\le 15$|$\le 20$|$= 0$| |3 ~ 5|$\le 20$|$\le 50$|$= 1$| |6, 7|$\le 200$|$\le 300$|$= 0$| |8, 9|$\le 2,000$|$= n - 1$|$= 1$| |10, 11|$\le 2,000$|$\le 3,000$|$= 0$| |12, 13|$\le 2,000$|$\le 3,000$|$= 1$| |14, 15|$\le 10^5$|$= n - 1$|$= 1$| |16, 17|$\le 10^5$|$\le 2 \times 10^5$|$= 0$| |18 ~ 20|$\le 10^5$|$\le 2 \times 10^5$|$= 1$|