题目描述

题目译自 XVI OI Olimpiada Informatyczna – II etap Przechadzka Bajtusia

Bajtuś 是拜托城最年幼的居民之一，刚刚学会读写，但已能独自上学。每天清晨，他从家出发，依次接上所有小伙伴，最后一起前往学校。

某天，Bajtuś 的老师要求他记录从家到学校的街道列表，并在下次课上朗读。然而，完整记录可能耗费大量纸张。于是，约定只记录每条街道名称的首字母。拜托城的每条街道为单向，连接两个不同交叉口。

Bajtuś 朗读时，仅在接小伙伴的地点停顿。因此，他从家到学校的路径可分为若干段，每段的街道首字母序列视为一个单词。Bajtuś 阅读尚不熟练，常从右向左读，例如 mleko 可能读成 okelm。他的父母深知这一问题，决定帮他规划一条特殊路径：每段路径的首字母序列无论正读反读都相同，且每段路径尽量短。他们向你求助。

编写程序，完成以下任务：

• 从标准输入读取城市描述。
• 规划从家到学校的路径，使每段路径最短，且其首字母序列为回文。
• 在标准输出中输出每段路径的长度及其首字母序列。

输入格式

第一行包含两个整数 $n, m$ $(2 \leq n \leq 400, 1 \leq m \leq 60000)$，分别表示拜托城的交叉口数和街道数。

接下来的 $m$ 行描述街道，第 $i+1$ 行包含三个值 $x_i, y_i, c_i$ $(1 \leq x_i, y_i \leq n, x_i \neq y_i)$，表示街道从交叉口 $x_i$ 到 $y_i$，首字母为小写英文字母 $c_i$。任意两交叉口间同方向最多有一条街道。

下一行包含一个整数 $d$ $(2 \leq d \leq 100)$，表示 Bajtuś 路径上的交叉口数。

最后一行包含 $d$ 个整数 $s_i$ $(1 \leq s_i \leq n)$，表示 Bajtuś 从家（交叉口 $s_1$）出发，依次经过小伙伴所在地（交叉口 $s_2, s_3, \ldots, s_{d-1}$），到达学校（交叉口 $s_d$）。相邻交叉口编号不同，但列表中可能有重复交叉口。若两相邻交叉口间无符合要求的路径，Bajtuś 将抄近路，不记录任何内容。

输出格式

输出 $d-1$ 行，第 $i$ 行包含一个整数 $r_i$ 和一个字符串 $w_i$，用单空格分隔。$r_i$ 表示从交叉口 $s_i$ 到 $s_{i+1}$ 的最短路径长度，满足题目要求；$w_i$ 为该路径上街道首字母序列。若无符合要求的路径，输出 $-1$。若有多条符合要求的 $w_i$，输出任意一条。

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