리스크 (Risk)

Risk는 여러 명의 플레이어가 서로 경쟁하며 세계 정복을 노리는 보드게임이다. 게임판은 여러 가상의 나라로 나뉜 세계 지도이며, 각 나라는 다른 나라들과 국경을 맞대고 있다. 자신의 차례에 플레이어는 한 나라에 주둔한 군대로 그 나라와 국경을 맞댄 나라만 공격할 수 있다. 어떤 나라를 정복하면 군대를 새로 정복한 그 나라로 이동시킬 수 있다.

플레이 도중 플레이어는 많은 군대를 시작 나라에서 목적지 나라로 옮기기 위해 정복을 여러 번 연달아 수행하곤 한다. 보통은 정복해야 하는 나라의 총 개수가 최소가 되도록 경유할 나라들을 고른다.

20개의 나라로 이루어진 게임판이 주어지며, 각 나라는 1개 이상 19개 이하의 다른 나라와 국경을 맞댄다. 시작 나라와 목적지 나라가 주어질 때, 목적지에 도달하기 위해 정복해야 하는 나라의 최소 개수를 구하여라. 이때 목적지 나라도 개수에 포함한다. 정복하는 나라의 순서를 출력할 필요는 없고 개수만 구하면 된다. 예를 들어 시작 나라와 목적지 나라가 서로 이웃이면 답은 1이다.

입력은 여러 개의 테스트 세트로 이루어진다. 각 테스트 세트는 1번째 줄부터 19번째 줄까지 게임판을 기술하고, 그 뒤에 질의 목록이 이어진다.

모든 국경을 두 번 나열하지 않기 위해, 나라 $I$와 나라 $J$ 사이의 국경은 더 작은 번호의 나라 줄에만 한 번 기록한다. 즉 $1 \le I \le 19$인 각 $I$에 대해, $I$번째 줄에는 나라 $I$와 국경을 맞댄 더 높은 번호의 나라 개수 $X$가 먼저 나오고, 이어서 서로 다른 정수 $J$ ($I < J \le 20$)가 $X$개 주어진다.

테스트 세트의 20번째 줄에는 이어지는 질의의 개수 $N$ ($1 \le N \le 100$)이 하나 주어진다. 다음 $N$개의 각 줄에는 두 정수 $A$와 $B$ ($1 \le A, B \le 20$, $A \ne B$)가 주어지며, 각각 한 질의의 시작 나라와 목적지 나라를 나타낸다.

입력에는 여러 개의 테스트 세트가 있을 수 있으며, 파일의 끝에 도달할 때까지 계속 읽어 처리해야 한다. 모든 게임판에서 임의의 두 나라 사이에는 적어도 하나의 경로가 존재한다.

각 테스트 세트에 대해 먼저 Test Set #T 형식의 줄을 출력한다. 여기서 $T$는 테스트 세트의 번호이며 1부터 시작한다.

그다음 각 질의에 대해 다음과 같이 고정 열 서식으로 결과 한 줄을 출력한다.

• 1~2열: 시작 나라 $A$ (너비 2, 오른쪽 정렬)
• 3~6열: 문자열 to
• 7~8열: 목적지 나라 $B$ (너비 2, 오른쪽 정렬)
• 9~10열: 문자열 :
• 11열부터: 나라 $A$에서 나라 $B$로 이동하기 위해 정복해야 하는 나라의 최소 개수 (왼쪽 정렬)

연속한 두 테스트 세트 사이에는 빈 줄을 하나 출력하여 구분한다.