[POI2009]Baj 最短回文路

时间限制:10s      空间限制:162MB

题目描述

N个点用M条有向边连接,每条边标有一个小写字母。 对于一个长度为D的顶点序列,回答每对相邻顶点Si到Si+1的最短回文路径。 如果没有,输出-1。 如果有,输出最短长度以及这个字符串。


输入格式

第一行正整数N和M ( 2 ≤ N ≤ 400 , 1 ≤ M ≤ 60,000 ) 接下来M行描述边的起点,终点,字母。接下来D表示询问序列长度 ( 2 ≤ D ≤ 100 ) 再接下来D个1到N的整数


输出格式

对于D-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

提示

没有写明提示


题目来源

没有写明来源