Home => ProblemSet => 100.2023-02:城市建造
1981: 100.2023-02:城市建造
Time Limit: 1 Sec Memory Limit: 512 MB Submit: 0 Solved: 0[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
在这个国度里面有 n 座城市，一开始城市之间修有若干条双向道路，导致这些城市形成了 t≥2 个连通块，特别的，这些连通块之间两两大小差的绝对值不超过 0≤k≤1。为了方便城市建设与发展，n 座城市中的某 t 座城市在这 t 座城市之间额外修建了至少一条双向道路，使得所有城市连通。
现在已经知道额外修建后的所有道路，你需要算出有哪些双向道路集合 E′，满足这些道路有可能是后来额外修建的，请输出答案对 998,244,353 取模的结果。
即给定一张 n 个点 m 条边的无向连通图 G=(V,E)，询问有多少该图的子图 G′=(V′,E′)，满足 E′≠∅ 且 G−E′ 中恰好有 ∣V′∣ 个连通块，且任意两个连通块大小之差不超过 k，保证 0≤k≤1，请输出答案对 998,244,353 取模的结果。
现在已经知道额外修建后的所有道路，你需要算出有哪些双向道路集合 E′，满足这些道路有可能是后来额外修建的，请输出答案对 998,244,353 取模的结果。
即给定一张 n 个点 m 条边的无向连通图 G=(V,E)，询问有多少该图的子图 G′=(V′,E′)，满足 E′≠∅ 且 G−E′ 中恰好有 ∣V′∣ 个连通块，且任意两个连通块大小之差不超过 k，保证 0≤k≤1，请输出答案对 998,244,353 取模的结果。
Input
输入的第一行包含三个正整数 n,m,k，分别表示城市数、修建后的道路数以及任意两个连通块大小之差的上限。
接下来 m 行每行包含两个正整数 u,v，表示城市 u 和 v 之间存在一条双向道路，保证 u≠v。
接下来 m 行每行包含两个正整数 u,v，表示城市 u 和 v 之间存在一条双向道路，保证 u≠v。
Output
输出一个数表示答案对 998,244,353 取模后的结果。
Sample Input Copy
4 4 1
1 2
2 3
1 3
3 4
Sample Output Copy
2
HINT
【样例 1 解释】
有以下两种情况：
更多样例：cities.zip
有以下两种情况：
- 本来只有 (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) 这四条道路，使得所有城市连通。
更多样例：cities.zip