우주선 방어 (Small)

적이 우주선에 침입했다. 뛰어난 전술만이 우주선을 지켜낼 수 있다. 병사가 우주선 안을 돌아다닐 때 쓰는 장치는 두 가지다. 순간이동기와 터보리프트다.

순간이동기는 병사를 즉시 다른 방으로 옮긴다. 모든 방에는 순간이동기가 하나씩 있고, 방마다 색이 하나씩 정해져 있다. 어떤 방에 있는 병사는 그 방의 순간이동기로 같은 색인 다른 방 어디로든 즉시 이동할 수 있다. 이때 걸리는 시간은 0초다.

터보리프트는 방과 방 사이를 더 느리게 오간다. 여러 방향으로 움직이는 승강기라고 보면 된다. 터보리프트 하나는 정해진 한 방에서 정해진 다른 한 방으로 병사를 옮기고, 옮기는 데 걸리는 시간이 정해져 있다. 터보리프트에는 다음 두 가지 성질이 있다.

• 터보리프트는 한 방향으로만 움직인다. 방 $a$에서 방 $b$로 병사를 옮기는 터보리프트가 있어도, 같은 터보리프트로 방 $b$에서 방 $a$로 갈 수는 없다. 그 방향으로 움직이는 터보리프트가 따로 있을 수는 있다.
• 여러 병사가 같은 터보리프트를 함께 쓸 수 있고, 서로 방해하지 않는다.

병사 여러 명의 현재 위치와 목적지가 주어진다. 각 병사가 현재 위치에서 목적지까지 가는 데 걸리는 최소 시간을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 우주선의 방 개수 $N$이 주어진다. 방 번호는 1번부터 $N$번까지다. 이어지는 $N$개의 줄에는 1번 방부터 $N$번 방까지의 색이 한 줄에 하나씩 문자열로 주어진다. 각 문자열은 알파벳 소문자 a부터 z까지와 숫자 0부터 9까지로만 이루어지고, 길이는 2 이하다.

다음 줄에는 터보리프트의 개수 $M$이 주어진다. 이어지는 $M$개의 줄에는 세 정수 $a_i$, $b_i$, $t_i$가 공백으로 구분되어 주어진다. 방 $a_i$에서 방 $b_i$로 병사를 $t_i$초 만에 옮기는 터보리프트가 있다는 뜻이다.

다음 줄에는 지휘하는 병사의 수 $S$가 주어진다. 이어지는 $S$개의 줄에는 병사 한 명의 현재 위치 $p_j$와 목적지 $q_j$가 공백으로 구분되어 주어진다.

제한은 다음과 같다.

• $1 \le T \le 10$
• $1 \le N \le 1000$
• $0 \le M \le 3000$
• $1 \le a_i, b_i \le N$
• $0 \le t_i \le 1000$
• $1 \le S \le 100$
• $1 \le p_j, q_j \le N$

각 테스트 케이스마다 먼저 Case #x: 형태의 줄을 하나 출력한다. 여기서 x는 테스트 케이스 번호이고 1부터 시작한다. 그 다음 $S$개의 줄에 정수를 하나씩 출력한다. $j$번째 줄에는 병사가 방 $p_j$에서 방 $q_j$까지 가는 데 걸리는 최소 시간을 초 단위로 출력한다. 방 $p_j$에서 방 $q_j$로 가는 경로가 없으면 -1을 출력한다.