초청 연사
시간 제한2초메모리 제한512 MB
평면 위에 x좌표와 y좌표가 각각 모두 다르고 세 점이 한 직선 위에 있지 않은 빨간 점 n개와 파란 점 n개가 주어질 때, 각 빨간 점과 파란 점을 짝지어 서로 교차하지 않는 n개의 꺾은선을 그린다.
문제
큰 학회에 n명의 초청 연사가 있다. 이들은 해당 분야를 이끄는 연구자들이다. 안타깝게도 이들은 서로를 극도로 증오한다. 누구도 다른 사람보다 늦게 발표하는 것을 참지 못한다. 그래서 이들 모두는 환영 파티 직후 동시에 강연을 해야 한다. 당신은 이들이 강연할 n개의 서로 다른 방과 파티를 위한 n개의 테이블을 마련했다. 학회장은 매우 넓어서 유클리드 평면으로 취급할 수 있고, 모든 테이블과 방은 이 평면 위의 점으로 볼 수 있다.
모든 방과 모든 테이블은 당연히 서로 구별되지 않으므로, 어떤 방이나 테이블이든 아무 과학자에게나 배정할 수 있다. 남은 문제는 이들이 한 지점에서 다른 지점으로 어떻게 이동하느냐이다. 두 연사의 경로가 교차하면 심각한 스캔들이 보장된다. 당신은 이들에게 어떤 경로를 따라야 하는지 아주 자세히 지시할 수 있지만, 이들은 직선을 따라서만 이동하는 것 같다. 따라서 n개의 테이블과 n개의 강연실을 꺾은선(연결된 선분들의 연속)으로 이어야 하며, 어떤 두 꺾은선도 서로 교차해서는 안 된다.
입력
첫 줄에는 테스트 케이스의 수 z가 주어진다 (1 ≤ z ≤ 200). 이어서 각 테스트 케이스의 설명이 주어진다.
각 테스트 케이스의 첫 줄에는 초청 연사의 수 n이 주어진다 (1 ≤ n ≤ 6). 다음 2n개의 줄에는 각각 두 정수 xi, yi가 주어진다 (|xi|, |yi| ≤ 100). 이는 i번째 지점의 좌표이다. 처음 n개의 지점은 테이블이고, 나머지는 강연실이다.
모든 xi는 서로 다르고, 모든 yi는 서로 다르며, 어떤 세 점도 한 직선 위에 있지 않다고 가정할 수 있다.
출력
각 테스트 케이스마다 n개의 꺾은선을 다음 형식으로 출력한다. 각 꺾은선마다 먼저 꼭짓점의 수 k를 출력한다. 그런 다음 k개의 줄에 이 꺾은선의 연속한 꼭짓점들의 좌표를 출력한다. 각 꺾은선의 양 끝은 입력으로 주어진 두 점, 즉 테이블 하나와 강연실 하나여야 한다. 어떤 꺾은선도 스스로 교차해서는 안 되고, 어떤 두 꺾은선도 공통점을 가져서는 안 된다. 특히 모든 입력 점은 어떤 꺾은선의 끝에 나타나야 한다. 또한 k는 100을 넘지 않아야 하고, 모든 점의 좌표는 −1000과 1000 사이여야 한다.