题目描述

小爱生活的城市可以看成一张$n$个点，$m$条道路的有向图，每一条道路旁的风景用一个小写字母表示，相同的小写字母表示相同的风景。为了更好的了解自己居住的城市，小爱便制定了旅行计划。他会按计划从起点$S_1$出发，前往第$2$个目的地$S_2$，再前往第$3$个目的地$S_3$...以此类推知道第$p$个目的地$S_p$。

但是迷上了穿越电影的小爱，趁此机会又想体验一把时光倒流的感觉，即他在从一个目的地到另一个目的地的过程中，经过道路的风景必须是中心对称的（即经过边的边权组成字符串必须回文）。

为了更快的完成计划，请你预先帮助小爱计算出，按他的设想，相邻目的地之间最少需要经过几条边，若无法满足条件，则输出-1。

输入格式

第一行：输入两个正整数$n,m$ 接下去$m$行，每行3个参数$u,v,w$,表示有一条边由$u$指向$v$，边权字母为$w$ 第$m+2$行，一个正整数$p$，表示旅行$p$个目的地 第$m+3$行，$p$个正整数，$S_1,S_2,S_3...S_p$

输出格式

输出共$p-1$行，其中第$i$行输出从$Si \rightarrow S_{i+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

数据范围

$1 \leq n \leq 400$ $1 \leq m \leq 60000$ $2 \leq p \leq 100$ $1 \leq u,v,S_i \leq n$