P6606 [Code+#7] Minimum Path String

In an undirected graph with $n$ vertices and $m$ edges, every vertex is labeled by a $6$-digit string starting from `0`, i.e., `000000`, `000001`, `000002`, $\ldots$, up to the $6$-digit string corresponding to $n-1$. It is guaranteed that $n \le 10^6$, so the $6$-digit labels will not overflow. For every vertex except `000000`, you need to find a path starting from `000000` that does not pass through any repeated vertex, such that the string formed by concatenating the digit strings of all vertices on the path in order is lexicographically smallest. To compare the lexicographical order of two different strings: if one string is a prefix of the other, then the shorter string is lexicographically smaller; otherwise, scan from left to right to find the first position where they differ, and the string with the smaller digit at that position is lexicographically smaller. Since outputting the path is too troublesome, you do not need to output the whole path. You only need to treat the concatenation of all vertex digit strings on the path as an integer, and output this number modulo $998244353$.

The first line contains two integers $n$ and $m$. The second line contains a digit string of length $12m$, which describes each edge in order. Each edge is represented by $12$ digits: the first $6$ digits and the last $6$ digits are the labels of the two vertices connected by this edge. Note that the input may contain self-loops or multiple edges.

Output $n-1$ lines. For each vertex other than `000000`, output the result of taking the lexicographically smallest path from `000000` to that vertex, treating the concatenated string as an integer and taking it modulo $998244353$. If a vertex is not reachable from `000000`, output $-1$ on the corresponding line instead.

### Sample Explanation - From `000000` to `000001`, the required path corresponds to the string `000000000002000001`. - From `000000` to `000002`, the required path corresponds to the string `000000000002`. - From `000000` to `000003`, the required path corresponds to the string `000000000002000001000003`, and after taking modulo $998244353$ it is $517560944$. - From `000000` to `000004`, there is no path. ### Subtasks Subtask $1$ ($11$ points) - $1 \le n \le 10^6, m = 0$. Subtask $2$ ($55$ points) - $1 \le n \le 10, 0 \le m \le 20$. Subtask $3$ ($34$ points) - $1 \le n \le 10^6, 0 \le m \le 10^6$. Translated by ChatGPT 5