题目背景

English Edition

题目描述

给出一张 $n$ 个点 $m$ 条边的有向图，每条边上有一个字母，并给出一个整数 $d$ 和一个序列 $s_1, s_2, \dots, s_d$。

你需要对每一个 $i(1\le i<n)$ 求出一条从 $s_i$ 到 $s_{i+1}$ 的最短路径满足这条路径上的边上的字母连起来后是回文的。

不保证每个点最多只在 $s$ 中出现一次。

输入格式

第一行两个整数 $n, m$。

之后 $m$ 行，每行两个整数 $x_i, y_i$ 与一个字母 $c_i$，表示有一条从 $x_i$ 到 $y_i$ 的边，这条边上的字母是 $c_i$。

之后一行一个整数 $d$。

之后一行 $d$ 个整数， 表示序列 $s$。

输出格式

输出共 $d-1$ 行，第 $i$ 行输出一条从 $s_i$ 到 $s_{i+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 ala
-1

提示

对于 $100\%$ 的数据，$2\le n\le 400$，$1\le m\le 6\times10^4$，$1\le x_i,y_i\le n$，$2\le d\le100$，$1\le s_i\le n$。

同时保证不会出现重边与自环。