{"problem":{"name":"[省选联考 2023] 城市建造","description":{"content":"在这个国度里面有 $n$ 座城市，一开始城市之间修有若干条双向道路，导致这些城市形成了 $t \\ge 2$ 个连通块，特别的，这些连通块之间两两大小差的绝对值不超过 $0 \\le k \\le 1$。为了方便城市建设与发展，$n$ 座城市中的某 $t$ 座城市**在这 $t$ 座城市之间**额外修建了至少一条双向道路，使得所有城市连通。 现在已经知道额外修建后的所有道路，你需要算出有哪些双向道路集","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9167"},"statements":[{"statement_type":"Markdown","content":"在这个国度里面有 $n$ 座城市，一开始城市之间修有若干条双向道路，导致这些城市形成了 $t \\ge 2$ 个连通块，特别的，这些连通块之间两两大小差的绝对值不超过 $0 \\le k \\le 1$。为了方便城市建设与发展，$n$ 座城市中的某 $t$ 座城市**在这 $t$ 座城市之间**额外修建了至少一条双向道路，使得所有城市连通。\n\n现在已经知道额外修建后的所有道路，你需要算出有哪些双向道路集合 $E'$，满足这些道路有可能是后来额外修建的，请输出答案对 $998,244,353$ 取模的结果。\n\n即给定一张 $n$ 个点 $m$ 条边的**无向连通**图 $G = (V, E)$，询问有多少该图的子图 $G' = (V', E')$，满足 $E' \\ne \\varnothing$ 且 $G - E'$ 中恰好有 $|V'|$ 个连通块，且任意两个连通块大小之差不超过 $k$，保证 $0 \\le k \\le 1$，请输出答案对 $998,244,353$ 取模的结果。\n\n## Input\n\n输入的第一行包含三个正整数 $n, m, k$，分别表示城市数、修建后的道路数以及任意两个连通块大小之差的上限。\n\n接下来 $m$ 行每行包含两个正整数 $u, v$，表示城市 $u$ 和 $v$ 之间存在一条双向道路，保证 $u \\ne v$。\n\n## Output\n\n输出一个数表示答案对 $998,244,353$ 取模后的结果。\n\n[samples]\n\n## Note\n\n**【样例 1 解释】**\n\n有以下两种情况：\n\n- 本来只有 $(3, 4)$ 这一条道路，此时有三个连通块，分别为 $\\{1\\}, \\{2\\}, \\{3, 4\\}$；后来城市 $1, 2, 3$ 决定在它们三座城市中额外修建了 $(1, 2), (2, 3), (1, 3)$ 这三条道路，使得所有城市连通。\n- 本来没有任何道路，此时有四个连通块，分别为 $\\{1\\}, \\{2\\}, \\{3\\}, \\{4\\}$；后来城市 $1, 2, 3, 4$ 决定在它们四座城市中额外修建了 $(1, 2), (2, 3), (1, 3), (3, 4)$ 这四条道路，使得所有城市连通。\n\n**【数据范围】**\n\n对于所有的数据，保证：$3 \\le n \\le 10^5$，$n - 1 \\le m \\le 2 \\times 10^5$，$0 \\le k \\le 1$。\n\n|测试点|$n$|$m$|$k$|\n|:-:|:-:|:-:|:-:|\n|1, 2|$\\le 15$|$\\le 20$|$= 0$|\n|3 ~ 5|$\\le 20$|$\\le 50$|$= 1$|\n|6, 7|$\\le 200$|$\\le 300$|$= 0$|\n|8, 9|$\\le 2,000$|$= n - 1$|$= 1$|\n|10, 11|$\\le 2,000$|$\\le 3,000$|$= 0$|\n|12, 13|$\\le 2,000$|$\\le 3,000$|$= 1$|\n|14, 15|$\\le 10^5$|$= n - 1$|$= 1$|\n|16, 17|$\\le 10^5$|$\\le 2 \\times 10^5$|$= 0$|\n|18 ~ 20|$\\le 10^5$|$\\le 2 \\times 10^5$|$= 1$|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9167","tags":["各省省选","2023","O2优化"],"sample_group":[["4 4 1\n1 2\n2 3\n1 3\n3 4\n","2\n"],["见附件中的 cities/cities2.in","见附件中的 cities/cities2.ans"],["见附件中的 cities/cities3.in","见附件中的 cities/cities3.ans"],["见附件中的 cities/cities4.in","见附件中的 cities/cities4.ans"]],"created_at":"2026-03-03 11:09:25"}}