题目描述

$N$ 个点用 $M$ 条有向边连接，每条边标有一个小写字母。

对于一个长度为 $D$ 的顶点序列，回答每对相邻顶点 $S_i$ 到 $S_i+1$的最短回文路径。

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

输入格式

第一行正整数 $N$ 和 $M$。

接下来 $M$ 行描述边的起点，终点，字母。

接下来 $D$ 表示询问序列长度再接下来 $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

数据规模与约定

$2 \le N \le 400 , 1 \le M \le 6 \times 10^4$

$2 \le D \le 100$