#6720. 「CodePlus #7」最小路径串

内存限制:512 MiB 时间限制:6000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

n 个点 m 条边的无向图中,所有点用从 0 开始的 6 位数字串编号,即 000000000001000002、……直到 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

样例解释

  • 000000000001 所求的路径对应的串为 000000000002000001
  • 000000000002 所求的路径对应的串为 000000000002
  • 000000000003 所求的路径对应的串为 000000000002000001000003,对 998244353 取模后为 517560944
  • 000000000004 不存在路径。

数据范围与提示

子任务 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