바이티 소년의 등굣길

바이티는 바이트버그에서 가장 어린 주민 가운데 한 명이다. 이제 막 읽고 쓰기를 배웠지만, 혼자서 학교에 갈 수 있을 만큼은 자랐다. 매일 아침 바이티는 집을 나서 친구들을 한 명씩 차례로 들르고, 모두가 모이면 그제서야 다 함께 학교로 향한다.

어느 날 선생님은 바이티에게 학교에 가는 길에 지나는 거리들의 목록을 만들어 다음 시간에 큰 소리로 읽어 오라고 했다. 목록이 너무 길어지지 않도록, 바이티는 지나는 각 거리 이름의 첫 글자만 적기로 했다. 바이트버그의 모든 거리는 일방통행이며, 서로 다른 두 교차로를 잇는다.

바이티는 친구를 만나는 교차로에서만 잠깐 멈추므로, 걷는 길의 각 구간(연속한 두 정차 지점 사이)은 하나의 단어가 된다. 아직 읽기가 서툴러서 왼쪽에서 오른쪽 대신 오른쪽에서 왼쪽으로 읽기도 하는데, 그래서 milk를 milk로도 klim으로도 읽을 수 있다. 부모님은 실수를 줄여 주려고, 모든 구간의 단어가 왼쪽으로 읽으나 오른쪽으로 읽으나 똑같은 회문이 되는 경로를 원한다. 또한 각 단어는 가능한 한 짧기를 바란다.

도시의 정보와 바이티가 멈추는 교차로들의 순서가 주어진다. 이웃한 두 정차 지점마다, 일방통행 거리들을 따라가는 경로 중 거리 첫 글자들의 열이 회문이 되는 가장 짧은 경로를 구하여라.

첫째 줄에 두 정수 $n$과 $m$이 주어진다 ($2 \le n \le 400$, $1 \le m \le 60000$). 각각 바이트버그의 교차로 수와 일방통행 거리의 수이다.

다음 $m$개의 줄에는 각각 두 정수와 한 글자 $x_i$ $y_i$ $c_i$가 주어진다 ($1 \le x_i \le n$, $1 \le y_i \le n$, $x_i \ne y_i$). 이는 교차로 $x_i$에서 교차로 $y_i$로 이어지고 이름이 소문자 알파벳 $c_i$로 시작하는 일방통행 거리를 뜻한다. 임의의 순서쌍에 대해 거리는 많아야 하나뿐이다. 즉 $x$에서 $y$로 가는 거리와 $y$에서 $x$로 가는 거리가 각각 많아야 하나이다.

그다음 줄에는 정수 $d$가 주어진다 ($2 \le d \le 100$). 바이티의 경로에 있는 교차로의 수이다.

마지막 줄에는 $d$개의 정수 $s_1, s_2, \ldots, s_d$가 주어진다 ($1 \le s_i \le n$). 바이티가 방문하는 순서대로의 교차로이며, $s_1$은 집, $s_d$는 학교이다. 이웃한 두 값은 항상 서로 다르지만, 이웃하지 않은 값끼리는 같을 수 있다.

$d - 1$개의 줄을 출력한다. $i$번째 줄에는 교차로 $s_i$에서 $s_{i+1}$로 가는 가장 짧은 회문 경로를 나타낸다. 먼저 그 길이 $r_i$(사용한 거리의 개수)를 출력하고, 공백 한 칸을 두고 그 경로를 따라 읽은 첫 글자들의 문자열 $w_i$를 출력한다. 경로가 회문이라는 것은 $w_i$를 왼쪽에서 오른쪽으로 읽으나 오른쪽에서 왼쪽으로 읽으나 같다는 뜻이며, 거리 하나로만 이루어진 경로도 회문으로 본다. 가장 짧은 회문 경로가 여러 개라면, 문자열 $w_i$가 사전순으로 가장 앞서는 것을 출력한다. $s_i$에서 $s_{i+1}$로 가는 회문 경로가 없으면 그 줄에 -1을 출력한다.