Problem Description

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$.

Input Format

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 Format

Output one number, the answer modulo $998,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

Hint

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$.

Translated by ChatGPT 5