데이터 제작

“정휘야, 데이터 만들어야지”

정휘는 원래 UCPC 2020 Call for Tasks에 점과 선분이 등장하는 재미있는 기하 문제를 제출하려고 했지만, 데이터를 너무 만들기 귀찮은 나머지 출제를 포기했다.
UCPC 2020에 문제를 꼭 출제하고 싶어 고민하고 있던 정휘는 아주 좋은 아이디어를 냈다. 바로 대회 참가자들에게 데이터를 만들게 하는 것이다! 원래는 정휘가 해야 할 일이었지만, 이제는 여러분이 좌표 평면상에 점 $N$개와 선분 $M$개를 적절히 배치해서 $K$개의 영역이 있는 데이터를 만들어야 한다.

영역은 평면 상의 빈 공간이며, 선분으로 모든 면이 둘러 쌓여 있어야 한다. 영역은 다른 영역으로 둘러 쌓여질 수도 있다. 좌표 범위가 너무 넓으면 계산하기 너무 힘들기 때문에, 79brue의 팬인 정휘는 모든 점의 좌표 범위를 $79$ 이하의 자연수로 제한하기로 했다!

여러분은 아래 조건을 모두 만족시키는 데이터를 만들어야 한다.

• 각 점의 $x$, $y$좌표는 $1$ 이상 $79$ 이하의 자연수가 되어야 한다.
• 모든 점의 위치는 서로 달라야 한다.
• 같은 두 점을 잇는 선분이 여러 개 존재하면 안 된다.
• 선분은 서로 다른 두 점을 이어야 한다.
• 서로 다른 두 선분은 끝점을 제외한 곳에서 교차하면 안 된다.
• 선분의 양 끝점을 제외한 점은 선분 위에 있으면 안 된다.

아래에서 (a)는 점 $3$개, 선분 $3$개로 $1$개의 영역을 만든 그림이고, (b)는 점 $4$개, 선분 $6$개로 $3$개의 영역을 만든 그림이다. (c)는 곡선이 존재하기 때문에, (d)는 교차하는 선분들이 존재하기 때문에 올바르지 않은 출력이다.

첫 번째 줄에 배치해야 할 점의 개수, 선분의 개수와 만들어야 하는 영역의 개수를 나타내는 세 자연수 $N,M,K$가 주어진다. ($3 \leq N \leq 3\ 000$, $0 \leq M$, $0 \leq K$)

 $N$개의 점과 $M$개의 서로 교차하지 않는 선분으로 $K$개의 다각형을 만들 수 있는 경우만 입력으로 주어진다.

첫째 줄부터 $N$번째 줄까지 $i$번째 줄에 $i$번째 점의 좌표를 출력한다. $N+1$번째 줄부터 $N+M$번째 줄까지 각 선분이 몇 번째 점을 연결하는지 출력한다.

\