P9535 [YsOI2023] Connected Graph Counting

A polynomial problem for Ysuperman’s template testing. [Data removed]

How many **undirected simple connected** graphs with $n$ vertices and $m$ edges are there, with no self-loops and no multiple edges, such that after deleting the vertex numbered $i$, the undirected graph is split into $a_i$ connected components. In particular, we guarantee $n-1 \le m \le n+1$, and the answer is not $0$. Output the answer modulo $998,244,353$.

The first line contains two integers $n, m$. The second line contains $n$ integers, where the $i$-th integer is $a_i$.

Output one integer per line, representing the result of the answer modulo $998,244,353$.

#### Explanation for Sample 1 There are three possible graphs. The four edges in each case are: 1. $(1,2),(1,3),(1,4),(2,3)$. 2. $(1,2),(1,3),(1,4),(2,4)$. 3. $(1,2),(1,3),(1,4),(3,4)$. #### Constraints |Test Point ID|$n,m$|Special Property| |:-:|:-:|:-:| |$1\sim 4$|$m=n-1$|None| |$5\sim 6$|$m=n$，$n\le 7$|None| |$7\sim 8$|$m=n$|$a_i=1$| |$9\sim 12$|$m=n$|None| |$13\sim 14$|$m=n+1$，$n\le 7$|None| |$15\sim 16$|$m=n+1$|$a_i=1$| |$17\sim 20$|$m=n+1$|None| For all testdata, it holds that $4 \le n \le 10^5$, $n-1 \le m \le n+1$, $1 \le a_i < n$, $n \le \sum_{i=1}^n a_i \le 2n-2$, and the answer is guaranteed to be non-zero. Translated by ChatGPT 5