P6606 [Code+#7] 最小路径串

$n$ 个点 $m$ 条边的无向图中，所有点用从 `0` 开始的 `6` 位数字串编号，即 `000000`、`000001`、`000002`、……直到 $n-1$ 对应的 $6$ 位数字串。保证 $n\le 10^6$，所以 $6$ 位的编号不会溢出。 对于除了 `000000` 以外的每个点，你需要找到一条从 `000000` 出发且不经过重复点的路径，使得路径上所有点的数字串顺次连接形成的串的字典序最小。比较两个不同的串的字典序的方法是：如果其中某个串是另一个的前缀，则较短的串字典序较小；否则，找出两个串从左往右扫描时遇到的首个不相等的位置，在这个位置上的数字较小的串字典序较小。 由于输出路径过于麻烦，你不需要完整地输出路径，只需要将路径上所有点的数字串视作一个整数，输出这个数对 $998244353$ 取模的结果。

第一行输入两个整数 $n$ 和 $m$。 第二行输入一个长度为 $12m$ 的数字串，依次表示每条边。每条边用 $12$ 个数字表示，其中前 $6$ 个与后 $6$ 个数字分别表示这条边所连接的两个点的编号。 注意，输入中可能会包含自环或重边。

输出 $n-1$ 行，依次输出除了点 `000000` 本身以外，点 `000000` 到每个点的字典序最小的路径，视为整数后对 $998244353$ 取模的结果。如果点 `000000` 不可到达某个点，则在对应的行改为输出 $-1$。

### 样例解释 - 从 `000000` 到 `000001` 所求的路径对应的串为 `000000000002000001`。 - 从 `000000` 到 `000002` 所求的路径对应的串为 `000000000002`。 - 从 `000000` 到 `000003` 所求的路径对应的串为 `000000000002000001000003`，对 $998244353$ 取模后为 $517560944$。 - 从 `000000` 到 `000004` 不存在路径。 ### 子任务 子任务 $1$（$11$ 分） - $1\le n\le 10^6, m = 0$。 子任务 $2$（$55$ 分） - $1\le n\le 10, 0\le m\le20$。 子任务 $3$（$34$ 分） - $1\le n\le 10^6, 0\le m\le 10^6$。