#P9167. [省选联考 2023] 城市建造

[省选联考 2023] 城市建造

题目描述

在这个国度里面有 nn 座城市,一开始城市之间修有若干条双向道路,导致这些城市形成了 t2t \ge 2 个连通块,特别的,这些连通块之间两两大小差的绝对值不超过 0k10 \le k \le 1。为了方便城市建设与发展,nn 座城市中的某 tt 座城市在这 tt 座城市之间额外修建了至少一条双向道路,使得所有城市连通。

现在已经知道额外修建后的所有道路,你需要算出有哪些双向道路集合 EE',满足这些道路有可能是后来额外修建的,请输出答案对 998,244,353998,244,353 取模的结果。

即给定一张 nn 个点 mm 条边的无向连通G=(V,E)G = (V, E),询问有多少该图的子图 G=(V,E)G' = (V', E'),满足 EE' \ne \varnothingGEG - E' 中恰好有 V|V'| 个连通块,且任意两个连通块大小之差不超过 kk,保证 0k10 \le k \le 1,请输出答案对 998,244,353998,244,353 取模的结果。

输入格式

输入的第一行包含三个正整数 n,m,kn, m, k,分别表示城市数、修建后的道路数以及任意两个连通块大小之差的上限。

接下来 mm 行每行包含两个正整数 u,vu, v,表示城市 uuvv 之间存在一条双向道路,保证 uvu \ne v

输出格式

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

4 4 1
1 2
2 3
1 3
3 4

2

见附件中的 cities/cities2.in
见附件中的 cities/cities2.ans
见附件中的 cities/cities3.in
见附件中的 cities/cities3.ans
见附件中的 cities/cities4.in
见附件中的 cities/cities4.ans

提示

【样例 1 解释】

有以下两种情况:

  • 本来只有 (3,4)(3, 4) 这一条道路,此时有三个连通块,分别为 {1},{2},{3,4}\{1\}, \{2\}, \{3, 4\};后来城市 1,2,31, 2, 3 决定在它们三座城市中额外修建了 (1,2),(2,3),(1,3)(1, 2), (2, 3), (1, 3) 这三条道路,使得所有城市连通。
  • 本来没有任何道路,此时有四个连通块,分别为 {1},{2},{3},{4}\{1\}, \{2\}, \{3\}, \{4\};后来城市 1,2,3,41, 2, 3, 4 决定在它们四座城市中额外修建了 (1,2),(2,3),(1,3),(3,4)(1, 2), (2, 3), (1, 3), (3, 4) 这四条道路,使得所有城市连通。

【数据范围】

对于所有的数据,保证:3n1053 \le n \le 10^5n1m2×105n - 1 \le m \le 2 \times 10^50k10 \le k \le 1

测试点 nn mm kk
1, 2 15\le 15 20\le 20 =0= 0
3 ~ 5 20\le 20 50\le 50 =1= 1
6, 7 200\le 200 300\le 300 =0= 0
8, 9 2,000\le 2,000 =n1= n - 1 =1= 1
10, 11 3,000\le 3,000 =0= 0
12, 13 =1= 1
14, 15 105\le 10^5 =n1= n - 1
16, 17 2×105\le 2 \times 10^5 =0= 0
18 ~ 20 =1= 1