로이드 레이지

게임 프로그램을 만들 때 두 다각형이 서로 겹치는지 판단해야 하는 경우가 자주 있다. 예를 들어 한 다각형이 우주선을, 다른 다각형이 거대한 운석을 나타내는 아케이드 게임에서 특히 유용하다.

주어진 다각형 집합에서 어떤 다각형들이 서로 교차하는지 판정하는 프로그램을 작성하여라.

첫 번째 줄에는 데이터 집합의 개수를 나타내는 정수 $n$이 주어진다. 각 데이터 집합은 다음과 같이 구성된다.

1. 분석할 다각형의 개수를 나타내는 양의 정수 $m$ ($1 \le m \le 10$)이 한 줄에 주어진다.
2. 이어서 다각형을 하나씩 나타내는 $m$개의 줄이 주어진다(첫 번째 줄이 다각형 1, 두 번째 줄이 다각형 2, ...). 각 줄은 그 다각형의 꼭짓점 개수를 나타내는 양의 정수 $v$ ($3 \le v \le 20$)로 시작하고, 그 뒤에 x,y 형식의 정수 좌표쌍 $v$개 ($0 \le x, y \le 100$)가 이어진다. 꼭짓점은 주어진 순서대로 변으로 연결되며, 마지막 꼭짓점은 다시 첫 번째 꼭짓점과 연결된다. 모든 다각형은 자기 자신과 교차하지 않는 단순 다각형이다.

각 데이터 집합에 대해 먼저 Data Set #z 형식의 제목을 출력한다. 여기서 $z$는 첫 번째 데이터 집합이면 1, 두 번째면 2, ... 이다. 해당 집합에 교차하는 다각형이 하나도 없으면 no collisions를 한 줄에 출력한다. 그렇지 않으면 교차하는 모든 다각형 쌍을 한 줄에 하나씩 출력하되, 항상 번호가 더 작은 다각형을 먼저 쓴다. 쌍은 번호가 작은 다각형을 우선 기준으로, 그다음 큰 다각형을 기준으로 오름차순 정렬하여 출력한다.

두 다각형이 교차한다는 것은, 내부 영역을 공유하거나(서로 겹침), 경계점을 공유하는(한 점에서 닿거나 한 변을 따라 닿음) 경우를 뜻한다.