[POI2009]Baj 最短回文路

有 $N$ 个顶点和 $M$ 条有向边，每条边都标有一个小写英文字母。一条路径的标签字符串由路径上各条边的字母依次连接而成。若该字符串是回文串，则称这条路径为回文路径。

给定一个长度为 $D$ 的顶点序列 $S_1,S_2,\ldots,S_D$。对于每对相邻顶点 $S_i$ 和 $S_{i+1}$，求从 $S_i$ 到 $S_{i+1}$ 的最短回文路径长度。若不存在这样的路径，则输出 $-1$。

输入格式

第一行包含两个正整数 $N$ 和 $M$，分别表示顶点数和有向边数。

接下来 $M$ 行，每行包含两个整数和一个小写英文字母，依次表示一条有向边的起点、终点和标记字母。

接下来输入一个整数 $D$，表示询问序列的长度。

最后输入 $D$ 个整数 $S_1,S_2,\ldots,S_D$，表示给定的顶点序列。

输出格式

对于序列中的 $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

数据范围

• $2\le N\le 400$；
• $1\le M\le 6\times 10^4$；
• $2\le D\le 100$；
• $1\le S_i\le N$。

来源与许可

本题为 POI 2009 试题「Baj 最短回文路」，题面与测试数据整理自 BZOJ。

样例 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