Description

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

Input Format

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 Format

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.

5 5
000000000003000001000003000001000002000002000000000002000003

2000001
2
517560944
-1

Hint

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