最小路径串 - Problem

$n$ 个点 $m$ 条边的无向图中，所有点用从 0 开始的 6 位数字串编号，即 000000、000001、000002、……直到 $n-1$ 对应的 6 位数字串。保证 $n \leq 10^6$，所以 6 位的编号不会溢出。

对于除了 000000 以外的每个点，你需要找到一条从 000000 出发且不经过重复点的路径，使得路径上所有点的数字串顺次连接形成的串的字典序最小。

比较两个不同的串的字典序的方法是：如果其中某个串是另一个的前缀，则较短的串字典序较小；否则，找出两个串从左往右扫描时遇到的首个不相等的位置，在这个位置上的数字较小的串字典序较小。

由于输出路径过于麻烦，你不需要完整地输出路径，只需要将路径上所有点的数字串视作一个整数，输出这个数对 998244353 取模的结果。

从标准输入读入数据。

第一行输入两个整数 $n$ 和 $m$。

第二行输入一个长度为 $12m$ 的数字串，依次表示每条边。每条边用 $12$ 个数字表示，其中前 $6$ 个与后 $6$ 个数字分别表示这条边所连接的两个点的编号。

注意，输入中可能会包含自环或重边。

输出到标准输出。

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

如果点 000000 不可到达某个点，则在对应的行改为输出 -1。

5 5
000000000003000001000003000001000002000002000000000002000003

从 000000 到 000001 所求的路径对应的串为 000000000002000001。
从 000000 到 000002 所求的路径对应的串为 000000000002。
从 000000 到 000003 所求的路径对应的串为 000000000002000001000003，对 998244353 取模后为 517560944。
从 000000 到 000004 不存在路径。

$1 \leq n \leq 10^6, m=0$。

$1 \leq n \leq 10, 0 \leq m \leq 20$。

$1 \leq n \leq 10^6, 0 \leq m \leq 10^6$。

QOJ.ac