A6640. 「联合省选 2023」城市建造
编程题
NOI/NOI+/CTSC
知识点
题目描述
在这个国度里面有 $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$ 取模的结果。
现在已经知道额外修建后的所有道路，你需要算出有哪些双向道路集合 $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$。
接下来 $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
说明/提示
对于所有的数据，保证：$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$|
|测试点|$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$|