P3485 [POI 2009] BAJ-The Walk of Bytie-boy

[English Edition](/paste/9lmt83m9)

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

第一行两个整数 $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`，否则输出这条路径上的所有字母。 如果有多条满足条件的路径，任意输出一条即可。

对于 $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$。 同时保证不会出现重边与自环。