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

문제

이 세상에는 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개의 줄에 걸쳐서 각 문제의 정답(국경을 건너는 회수의 최솟값)을 출력한다

예제 입력 1

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

예제 출력 1

2
1
W3sicHJvYmxlbV9pZCI6IjE4MjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMzhcdWFlMDgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc3NCBcdWMxMzhcdWMwYzFcdWM1ZDBcdWIyOTQgQ1x1YWMxY1x1Yzc1OCBcdWIwOThcdWI3N2NcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViMDk4XHViNzdjXHViNGU0XHVjNzQwIE5cdWFjMWNcdWM3NTggXHVhZjJkXHVjOWQzXHVjODEwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0IFx1YzgzOCBcdWM3ODhcdWIyZTQuICgzXHVjYzI4XHVjNmQwIFx1Yzg4Y1x1ZDQ1Y1x1YWNjNCkgXHViMmY5XHVjMmUwXHVjNzQwIEFcdWJjODggXHViMDk4XHViNzdjXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU1OFx1YzVlYyBCXHViYzg4IFx1YjA5OFx1Yjc3Y1x1YWU0Y1x1YzljMCBcdWM3NzRcdWIzZDlcdWM3NDQgXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gKFx1YWQ2ZFx1YWMwMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBDIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuKSBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVhZDZkXHVhY2JkXHVjNzQ0IFx1YWM3NFx1YjExMCBcdWI1NGMgXHViOWM4XHViMmU0IFx1YzEzOFx1YWUwOFx1Yzc0NCBcdWIwYjRcdWM1N2MgXHVkNTU4XHViYmMwXHViODVjIFx1YWQ2ZFx1YWNiZFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWIyOTQgXHVkNjhjXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1ZDY1NCBcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHViMDk4XHViNzdjXHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWI0ZTRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODM4IFx1Yzc4OFx1Yzc0NCBcdWI1NGMgXHVhZDZkXHVhY2JkXHVjNzQ0IFx1YWM3NFx1YjEwOFx1YjI5NCBcdWQ2OGNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjA5OFx1Yjc3Y1x1YjRlNFx1YjA3Y1x1YjlhYyBcdWM2MDFcdWM1ZWRcdWM3NDQgXHVhY2Y1XHVjNzIwXHVkNTU4XHVjOWMwXHViMjk0IFx1YzU0YVx1YzczY1x1YjA5OCwgXHViY2MwXHVjNzQ0IFx1YWNmNVx1YzcyMFx1ZDU2MCBcdWMyMThcdWIyOTQgXHVjNzg4XHViMmU0LiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIwOThcdWI3N2NcdWM3NTggXHVhYzFjXHVjMjE4IEMoMSZsZTtDJmxlOzYsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIEMrMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgQ1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhM2NcdWM4MDAgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBuKDEmbGU7biZsZTsyMCkgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCBuKjMgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCB4MSwgeTEsIHoxLCB4MiwgeTIsIHoyLCAuLi4sIHhuLCB5biwgem5cdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IHhrLCB5aywgemtcdWIyOTQgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBDKzJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWFjMWNcdWMyMTggUSgwJmx0O1EmbGU7MjApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gQyszXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBDK1ErMiBcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIFFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMFx1YzExYyBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBhLCBiIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGFcdWIyOTQgXHVjZDljXHViYzFjXHVkNTU4XHViMjk0IFx1YWQ2ZFx1YWMwMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzRcdWFjZTAgYlx1YjI5NCBcdWIzYzRcdWNjMjlcdWQ1NThcdWIyOTQgXHVhZDZkXHVhYzAwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YjJlNC4gKDEmbGU7YSwgYiZsZTtDKSIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgUVx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgUVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YWMwMSBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODE1XHViMmY1KFx1YWQ2ZFx1YWNiZFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWIyOTQgXHVkNjhjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMilcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTgyOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRyYXZlbGluZyBTYWxlc21hbiIsImRlc2NyaXB0aW9uIjoiPHA+TG9uZyBiZWZvcmUgdGhlIGRheXMgb2YgaW50ZXJuYXRpb25hbCB0cmFkZSB0cmVhdGllcywgYSBzYWxlc21hbiB3b3VsZCBuZWVkIHRvIHBheSB0YXhlcyBhdCBldmVyeSBib3JkZXIgY3Jvc3NlZC4gU28geW91ciB0YXNrIGlzIHRvIFx1ZmIwMW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiBib3JkZXJzIHRoYXQgbmVlZCB0byBiZSBjcm9zc2VkIHdoZW4gdHJhdmVsaW5nIGJldHdlZW4gdHdvIGNvdW50cmllcy4gV2UgbW9kZWwgdGhlIHN1cmZhY2Ugb2YgRWFydGggYXMgYSBzZXQgb2YgcG9seWdvbnMgaW4gdGhyZWUgZGltZW5zaW9ucyBmb3JtaW5nIGEgY2xvc2VkIGNvbnZleCAzRCBzaGFwZSwgd2hlcmUgZWFjaCBwb2x5Z29uIGNvcnJlc3BvbmRzIHRvIG9uZSBjb3VudHJ5LiBZb3UgYXJlIG5vdCBhbGxvd2VkIHRvIGNyb3NzIGF0IHBvaW50cyB3aGVyZSBtb3JlIHRoYW4gdHdvIGNvdW50cmllcyBtZWV0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+RWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBsaW5lIGNvbnRhaW5pbmcgYywgdGhlIG51bWJlciBvZiBjb3VudHJpZXMgKDQgJmxlOyBjICZsZTsgNjAwMCksIGZvbGxvd2VkIGJ5IGMgbGluZXMgY29udGFpbmluZyB0aGUgaW50ZWdlcnMgbiB4PHN1Yj4xPFwvc3ViPiB5PHN1Yj4xPFwvc3ViPiB6PHN1Yj4xPFwvc3ViPiAuIC4gLiB4PHN1Yj5uPFwvc3ViPiB5PHN1Yj5uPFwvc3ViPiB6PHN1Yj5uPFwvc3ViPiwgZGVzY3JpYmluZyAoaW4gb3JkZXIpIHRoZSBuIGNvcm5lcnMgb2YgYSBjbG9zZWQgcG9seWdvbiAoMyAmbGU7IG4gJmxlOyAyMCkuIFRoZW4gZm9sbG93cyBhIGxpbmUgd2l0aCBvbmUgaW50ZWdlciBtICgwICZsdDsgbSAmbGU7IDUwKSwgYW5kIHRoZW4gbSBsaW5lcyB3aXRoIHF1ZXJpZXMgYzxzdWI+YTxcL3N1Yj4gYzxzdWI+YjxcL3N1Yj4gLCB3aGVyZSBjPHN1Yj5hPFwvc3ViPiBhbmQgYzxzdWI+YjxcL3N1Yj4gYXJlIGNvdW50cnkgbnVtYmVycyAoc3RhcnRpbmcgd2l0aCAxKS4gTm8gcG9pbnQgd2lsbCBiZSBvbiB0aGUgbGluZSBiZXR3ZWVuIHR3byBjb25uZWN0ZWQgcG9pbnRzLCBhbmQgJm1pbnVzOzEwPHN1cD42PFwvc3VwPiAmbGU7IHgsIHksIHogJmxlOyAxMDxzdXA+NjxcL3N1cD4gZm9yIGFsbCBwb2ludHMuIE5vIHR3byBub24tYWRqYWNlbnQgZWRnZXMgb2YgYSBjb3VudHJ5IHNoYXJlIGEgY29tbW9uIHBvaW50LiBUaGUgaW5wdXQgaXMgdGVybWluYXRlZCBieSBhIGNhc2Ugd2hlcmUgYyA9IDAsIHdoaWNoIHNob3VsZCBub3QgYmUgcHJvY2Vzc2VkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHF1ZXJ5LCBvdXRwdXQgdGhlIG51bWJlciBvZiBib3JkZXJzIHlvdSBtdXN0IGNyb3NzIHRvIGdvIGZyb20gYzxzdWI+YTxcL3N1Yj4gdG8gYzxzdWI+YjxcL3N1Yj4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d