P9167 [NOI Qualifier Joint Contest 2023] City Construction

In this country, there are $n$ cities. At the beginning, there are some bidirectional roads between the cities, which makes these cities form $t \ge 2$ connected components. In particular, for any two components, the absolute difference of their sizes is at most $0 \le k \le 1$. To make city construction and development easier, among the $n$ cities, some $t$ cities built at least one additional bidirectional road **among these $t$ cities**, so that all cities become connected. Now all roads after adding are known. You need to determine which sets of bidirectional roads $E'$ could possibly be the roads added later. Output the result modulo $998,244,353$. That is, given an **undirected connected** graph $G = (V, E)$ with $n$ vertices and $m$ edges, ask how many subgraphs $G' = (V', E')$ satisfy $E' \ne \varnothing$, and $G - E'$ has exactly $|V'|$ connected components, and the size difference between any two connected components is at most $k$. It is guaranteed that $0 \le k \le 1$. Output the result modulo $998,244,353$.

The first line contains three positive integers $n, m, k$, representing the number of cities, the number of roads after construction, and the upper bound on the size difference between any two connected components. The next $m$ lines each contain two positive integers $u, v$, indicating that there is a bidirectional road between city $u$ and city $v$. It is guaranteed that $u \ne v$.

Output one number, the answer modulo $998,244,353$.

**Sample 1 Explanation** There are the following two cases: - Originally there was only the edge $(3, 4)$. Then there are three connected components: $\{1\}$, $\{2\}$, $\{3, 4\}$. Later, cities $1, 2, 3$ decided to additionally build the three edges $(1, 2)$, $(2, 3)$, $(1, 3)$ among these three cities, making all cities connected. - Originally there were no edges at all. Then there are four connected components: $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$. Later, cities $1, 2, 3, 4$ decided to additionally build the four edges $(1, 2)$, $(2, 3)$, $(1, 3)$, $(3, 4)$ among these four cities, making all cities connected. **Constraints** For all testdata, it is guaranteed that: $3 \le n \le 10^5$, $n - 1 \le m \le 2 \times 10^5$, $0 \le k \le 1$. |Test Point|$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$| Translated by ChatGPT 5