bzoj#P1138. [POI2009]Baj 最短回文路

[POI2009]Baj 最短回文路

题目描述

NN 个点用 MM 条有向边连接,每条边标有一个小写字母。

对于一个长度为 DD 的顶点序列,回答每对相邻顶点 SiS_iSi+1S_i+1的最短回文路径。

如果没有,输出 1-1。 如果有,输出最短长度以及这个字符串。

输入格式

第一行正整数 NNMM

接下来 MM 行描述边的起点,终点,字母。

接下来 DD 表示询问序列长度再接下来 DD11NN 的整数。

输出格式

对于 D1D-1 对相邻点,按要求输出一行。如果没合法方案,输出 1-1

6 7
1 2 a
1 3 x
1 4 b
2 6 l
3 5 y
4 5 z
6 5 a
3
1 5 3
3
-1

数据规模与约定

2N400,1M6×1042 \le N \le 400 , 1 \le M \le 6 \times 10^4

2D1002 \le D \le 100