题目描述

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

样例

5 5
000000000003000001000003000001000002000002000000000002000003

2000001
2
517560944
-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$。