웜홀

지구에서 인류에게 남은 시간이 얼마 없다. 쿠퍼와 아멜리아는 별들 사이에 인류의 미래가 있는지 확인하려고 이 은하 밖으로 나가는 임무에 자원했다. 천문학자들은 사람이 살 만한 행성을 여러 개 찾아냈고, 그중 몇 쌍이 웜홀로 이어져 있다는 사실도 알아냈다. 웜홀을 타고 이동하면 이동 거리는 0이다. 그 밖의 두 행성 사이를 이동하는 거리는 두 행성의 유클리드 거리다.

행성과 웜홀이 주어질 때, 질의로 주어진 두 행성 사이의 최단 이동 거리를 구하라.

• 첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 10$)가 주어진다.
• 각 테스트 케이스는 행성 목록, 웜홀 목록, 질의 목록으로 이루어진다.
• 행성 목록의 첫 줄에 행성의 수 $p$ ($1 \le p \le 60$)가 주어진다. 이어지는 $p$개의 줄에 행성의 이름과 정수 좌표가 name x y z 형식으로 주어진다 ($0 \le x, y, z \le 2 \times 10^6$). 이름은 ASCII 알파벳과 숫자로만 이루어지고 항상 알파벳으로 시작하며, 길이는 50자를 넘지 않는다. 이름은 대소문자를 구분한다. 즉 Earth와 earth는 서로 다른 행성이다. 좌표의 단위는 파섹이다.
• 웜홀 목록의 첫 줄에 웜홀의 수 $w$ ($0 \le w \le 40$)가 주어진다. 이어지는 $w$개의 줄에 웜홀 하나를 나타내는 두 행성 이름이 공백으로 구분되어 주어진다. 앞의 이름이 입구, 뒤의 이름이 출구다. 웜홀은 입구에서 출구 방향으로만 지날 수 있고, 출구로 들어갈 수는 없다. 두 이름은 모두 앞의 행성 목록에 나온 이름이다.
• 질의 목록의 첫 줄에 질의의 수 $q$ ($1 \le q \le 20$)가 주어진다. 이어지는 $q$개의 줄에 두 행성 이름이 공백으로 구분되어 주어진다. 두 이름은 모두 행성 목록에 나온 이름이며, 같은 이름이 두 번 나올 수도 있다.

각 테스트 케이스마다 먼저 Case i:를 한 줄에 출력한다. 여기서 $i$는 테스트 케이스의 번호이고 1부터 시작한다.

그다음 그 테스트 케이스의 질의마다 한 줄에 The distance from planet1 to planet2 is d parsecs.를 출력한다. planet1과 planet2는 질의에 주어진 이름을 그대로 쓰고, d는 planet1에서 planet2로 가는 최단 이동 거리를 가장 가까운 정수로 반올림한 값이다. 값이 정확히 두 정수의 중간이면 큰 쪽으로 올린다.