32525번 - Duality 스페셜 저지

문제

2ドル$차원 평면 위에 주어진 $N$개의 점 각각을 한 끝점으로 하고, 주어지지 않은 점을 다른 끝점으로 하는 선분을 $N$개 만들어 서로 교차하지 않게 해 보자. 2ドルN$개의 점은 모두 정수 좌표의 점이며, 서로 같은 좌표에 있으면 안 된다.

어떤 선분의 끝점이 다른 선분 위에 있거나, 두 선분이 끝점에서 만나면 교차하는 경우로 본다.

입력

총 $T$개의 테스트 케이스가 입력으로 주어지며, 첫째 줄에 $T$가 주어진다. $(1 \le T \le 1,000円)$

테스트 케이스의 첫째 줄에 $N$이 주어진다. $(1 \le N \le 100)$

테스트 케이스의 둘째 줄부터 $N$개의 점이 주어진다. 그중 $i$번째 줄에는 $i$번 점의 좌표 정수 $x_i,ドル $y_i$가 공백으로 구분되어 주어진다. $(-10^8 \le x_i, y_i \le 10^8)$

주어지는 모든 점의 좌표는 서로 다르다.

입력으로 주어지는 점들을 이용해 선분 $N$개를 서로 교차하지 않게 항상 만들 수 있음을 보장한다.

출력

각 테스트 케이스마다 $N$개의 줄에 걸쳐 교차하지 않는 $N$개의 선분을 출력한다.

그중 $j$번째 줄에는 주어진 점의 번호 $p_j$와 주어지지 않은 점의 좌표 정수 $x_j,ドル $y_j$를 공백으로 구분하여 출력한다. 이는 주어진 $p_j$번 점과 $(x_j, y_j)$의 점이 선분을 이루었다는 의미이다. 출력하는 $p_j$는 서로 달라야 한다. $(1 \le p_j \le N$; $-10^9 \le x_j, y_j \le 10^9)$

가능한 경우가 여럿인 경우는 그중 아무거나 하나를 출력한다.

제한

힌트