우주선 방어

적이 당신의 우주선을 침공했으며, 우월한 전술만이 우주선을 방어할 수 있게 해 줄 것이다! 병사들은 우주선 안을 이동하기 위해 순간이동 장치와 터보리프트라는 두 가지 장치를 사용한다.

순간이동 장치를 사용하면 병사들이 방 사이를 즉시 이동할 수 있다. 모든 방에는 순간이동 장치가 있으며, 방은 색으로 구분되어 있다. 병사가 어떤 색의 방에 있다면, 그 방의 순간이동 장치를 사용해 같은 색의 다른 어떤 방으로든 즉시 이동할 수 있다.

터보리프트를 사용하면 병사들이 방 사이를 더 느리게 이동할 수 있다. 터보리프트는 여러 방향으로 움직이는 엘리베이터와 같다. 각 터보리프트는 한 방에서 다른 한 방으로 이동하며, 이동에는 일정한 시간이 걸린다. 터보리프트에 관한 참고 사항은 다음과 같다.

• 터보리프트는 양방향이 아니다. 어떤 터보리프트가 병사들을 방 a에서 방 b(으)로 이동시킨다면, 같은 터보리프트로 병사들을 방 b에서 방 a(으)로 이동시킬 수 없다. 단, 그렇게 이동시키는 다른 터보리프트가 있을 수는 있다.

• 둘 이상의 병사가 같은 터보리프트를 사용할 수 있으며, 병사들은 어떤 방식으로도 서로에게 영향을 주지 않는다.

여러 병사의 현재 위치와 목적지가 주어진다. 각 병사에 대해, 그 병사가 현재 위치에서 목적지까지 이동하는 데 걸릴 수 있는 최소 시간을 출력한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

1 ≤ S ≤ 100. 1 ≤ $a_{i}$, $b_{i}$ ≤ N. 0 ≤ $t_{i}$ ≤ 1000. 1 ≤ $p_{j}$, $q_{j}$ ≤ N.

테스트 세트 1 - 공개

1 ≤ T ≤ 10. 1 ≤ N ≤ 1000. 0 ≤ M ≤ 3000.

테스트 세트 2 - 비공개

T = 1. 1 ≤ N ≤ 80000. 0 ≤ M ≤ 3000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스에 대해 다음이 주어진다.

각 테스트 케이스의 첫 번째 줄에는 우주선에 있는 방의 수를 나타내는 정수 N이 주어진다. 방에는 1부터 N까지 번호가 매겨져 있다. 이어지는 N개의 줄에는 각각 방 1부터 방 N까지 각 방의 색을 나타내는 문자열이 주어진다. 문자열에는 문자 a-z(영어 소문자)와 0-9(0부터 9까지의 숫자)만 포함되며, 각 문자열의 길이는 2 이하이다.

테스트 케이스의 다음 줄에는 우주선에 있는 터보리프트의 수를 나타내는 정수 M이 주어진다. 이어지는 M개의 줄에는 각각 공백으로 구분된 정수 3개인 $a_{i}$, $b_{i}$, $t_{i}$가 주어진다. 이는 병사들을 방 $a_{i}$에서 방 $b_{i}$(으)로 $t_{i}$초 만에 운송할 수 있는 터보리프트가 있음을 나타낸다.

테스트 케이스의 다음 줄에는 지휘하는 병사의 수를 나타내는 정수 S가 주어진다. 이어지는 S개의 줄에는 각각 한 병사의 위치와 목적지를 나타내는 두 정수 $p_{j}$와 $q_{j}$가 주어진다.

각 테스트 케이스에 대해 문자열 "Case #x:"만 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이다. 이어지는 S개의 줄에는 각각 정수 하나를 출력한다. j번째 줄에는 병사가 $p_{j}$에서 $q_{j}$(으)로 이동하는 데 걸릴 수 있는 최소 초를 출력한다. $p_{j}$에서 $q_{j}$(으)로 가는 경로가 없다면 -1을 출력해야 한다.