시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 0 0 0 0.000%

문제

이 세상에는 C개의 나라가 있다. 각각의 나라들은 N개의 꼭지점으로 이루어진 다각형으로 이루어 져 있다. (3차원 좌표계) 당신은 A번 나라에서 출발하여 B번 나라까지 이동을 하려 한다. (국가의 번호는 1부터 C 사이의 정수이다.) 그런데 국경을 건널 때 마다 세금을 내야 하므로 국경을 건너는 회수를 최소화 하려 한다. 각 나라의 꼭지점의 좌표들이 주어져 있을 때 국경을 건너는 회수를 구하는 프로그램을 작성하시오. 나라들끼리 영역을 공유하지는 않으나, 변을 공유할 수는 있다.

입력

첫째 줄에 나라의 개수 C(1≤C≤6,000)이 주어지고, 두 번째 줄부터 C+1번째 줄까지 C개의 줄에 걸쳐서 각 줄에는 다음과 같은 정보가 주어진다. 먼저 꼭지점의 개수 n(1≤n≤20) 이 주어지고 n*3 개의 정수 x1, y1, z1, x2, y2, z2, ..., xn, yn, zn가 순서대로 주어진다. 각각의 xk, yk, zk는 꼭지점의 좌표를 의미한다. 그리고 C+2번째 줄에 문제의 개수 Q(0<Q≤20)가 주어진다. C+3번째 줄부터 C+Q+2 번째 줄까지 Q개의 줄에 걸쳐서 두 개의 정수 a, b 가 주어진다. a는 출발하는 국가의 번호이고 b는 도착하는 국가의 번호이다. (1≤a, b≤C)

출력

첫째 줄부터 Q번째 줄까지 Q개의 줄에 걸쳐서 각 문제의 정답(국경을 건너는 회수의 최소값)을 출력한다

예제 입력

6
4 0 0 0 0 0 1 0 1 1 0 1 0
4 1 0 0 1 0 1 1 1 1 1 1 0
4 0 0 0 1 0 0 1 0 1 0 0 1
4 0 1 0 1 1 0 1 1 1 0 1 1
4 0 0 0 0 1 0 1 1 0 1 0 0
4 0 0 1 0 1 1 1 1 1 1 0 1
2
1 2
1 3

예제 출력

2
1

힌트