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

「CodePlus #7」最小路径串

题目描述

nn 个点 mm 条边的无向图中,所有点用从 0 开始的 6 位数字串编号,即 000000000001000002、……直到 n1n-1 对应的 66 位数字串。保证 n106n\le 10^6,所以 66 位的编号不会溢出。

对于除了 000000 以外的每个点,你需要找到一条从 000000 出发且不经过重复点的路径,使得路径上所有点的数字串顺次连接形成的串的字典序最小。比较两个不同的串的字典序的方法是:如果其中某个串是另一个的前缀,则较短的串字典序较小;否则,找出两个串从左往右扫描时遇到的首个不相等的位置,在这个位置上的数字较小的串字典序较小。

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

输入格式

第一行输入两个整数 nnmm

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

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

输出格式

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

样例

5 5
000000000003000001000003000001000002000002000000000002000003
2000001
2
517560944
-1
  • 000000000001 所求的路径对应的串为 000000000002000001
  • 000000000002 所求的路径对应的串为 000000000002
  • 000000000003 所求的路径对应的串为 000000000002000001000003,对 998244353998244353 取模后为 517560944517560944
  • 000000000004 不存在路径。

数据范围与提示

子任务 111111 分)

  • 1n106,m=01\le n\le 10^6, m = 0

子任务 225555 分)

  • 1n10,0m201\le n\le 10, 0\le m\le20

子任务 333434 分)

  • 1n106,0m1061\le n\le 10^6, 0\le m\le 10^6