P6516 [QkOI#R1] Quark and Graph

What do you do when SPFA gets hacked by testdata? Are you free? Can you come and count?

You are given a labeled, simple, undirected, connected graph where all edge weights are $1$. It has $n$ vertices and $m$ edges. You are also given the shortest path distances from vertex $1$ to every vertex. Find how many different graphs (forms) satisfy these conditions. In particular, we define the shortest distance from vertex $1$ to vertex $1$ as $0$. Two graphs are considered different if and only if there exists at least one edge $(u,v)$ that appears in one graph but does not appear in the other. **Since little_sun is extremely strong, the testdata guarantees that there is at least one graph that satisfies the conditions.** Output the answer modulo $998244353$.

The first line contains two positive integers $n,m$, where $n$ is the number of vertices and $m$ is the number of edges. The second line contains $n$ non-negative integers $d_1,d_2,\cdots,d_n$, representing the shortest path distance from vertex $1$ to each vertex.

Output one line with one integer, the answer.

### Sample Explanation For the first sample, there are two forms: $\{(1,2),(1,3),(2,4)\}$ and $\{(1,2),(1,3),(3,4)\}$. For the second sample, I came up with a wonderful explanation, but unfortunately this blank space is too small to write it down. ### Constraints **This problem uses bundled tests.** - Subtask 1 (10 pts): $n\le 7$, $m\le 14$, time limit 1s. - Subtask 2 (20 pts): $n\le 50$, $m\le 600$, time limit 1s. - Subtask 3 (20 pts): $n\le 1000$, $m\le 5000$, time limit 1s. - Subtask 4 (50 pts): no special constraints, time limit 3s. For $100\%$ of the data: $n\le 10^5$, $m\le 2\times 10^5$. Let $t_i=\sum_j[d_j=i]$. It is also required that $\sum_{i}t_it_{i-1}\le 2\times 10^5$. **This problem forces O2 optimization to be enabled.** Translated by ChatGPT 5