거울 함정

바이테아사르 왕의 궁전에 거울에 비친 제 모습을 즐겨 들여다보는 유령이 나타났고, 왕은 이 유령을 없애고 싶어 한다. 왕의 계획은 거울 함정이다. 안쪽의 모든 벽이 거울로 덮인, 밝게 빛나는 밀폐된 방을 만드는 것이다. 방의 어느 모서리에나 레이저 총이나 레이저 감지기를 설치할 수 있다. 유령이 레이저 광선을 가로지르는 순간 경보가 울려 왕의 유령 퇴치대가 출동한다.

방은 직교 다각형이다. 이웃한 두 벽은 서로 수직이며, 모든 벽의 길이는 정수이다. 어떤 모서리에 설치한 레이저 총은 그 모서리가 이루는 각의 이등분선을 따라 (바닥과 평행한 평면에서) 광선을 쏜다. 모든 모서리가 두 벽이 이루는 직각이므로 이 광선은 항상 45도 방향으로 나아간다. 광선이 거울 벽에 닿으면 통상적인 반사 법칙(입사각과 반사각이 같음)에 따라 반사되며, 여기서 그 각은 항상 45도이다.

이등분선을 따라 어떤 모서리로 곧장 들어가는 광선은 다음과 같이 동작한다.

• 그 모서리에 감지기가 있으면 광선은 완전히 흡수된다.
• 그 모서리에 감지기가 없으면(총은 있을 수 있다) 광선은 180도로 되돌아 반사된다.

그 밖의 모든 경우에는 광선이 방향을 전혀 바꾸지 않고 모서리를 그대로 지나친다.

광선 하나를 따라가 보면 결국 어떤 모서리의 이등분선을 따라 그 모서리에 도달한다. 이것이 모서리들을 짝지어 준다. 모서리 A에서 쏜 광선은 정확히 하나의 모서리 B에 도달하고, B에서 쏜 광선은 같은 경로를 되짚어 A로 돌아온다. 따라서 모서리들은 여러 쌍으로 나뉘며, 이 짝짓기는 방의 모양만으로 유일하게 정해진다.

가능한 한 많은 총과 감지기 쌍을 설치하려고 한다. 모든 총의 광선이 어떤 감지기에 흡수되고, 각 감지기는 정확히 하나의 광선만 흡수하며, 한 모서리에 총과 감지기를 함께 둘 수는 없다. 이러한 쌍의 최대 개수는 모서리 쌍의 개수와 같고, 그 쌍들의 모임은 유일하다.

모서리 1에서 모서리 7로 광선이 이동하는 거울 함정의 예.

방의 모양을 읽어 유일한 최적 배치를 계산해 출력하는 프로그램을 작성하라.

첫째 줄에 방의 벽 개수를 나타내는 정수 $n$ ($4 \le n \le 100000$)이 주어진다. 이어지는 $n$개의 줄에는 각각 $i$번째 모서리의 좌표를 나타내는 두 정수 $x_i$와 $y_i$ ($-1000000 \le x_i, y_i \le 1000000$)가 공백 하나로 구분되어 주어진다. 이웃한 두 모서리는 좌표축 중 하나와 평행한 벽으로 이어진다. 공통 모서리에서 만나는 이웃한 두 벽을 제외하면 어떤 두 벽도 점을 공유하지 않는다. 모서리들은 시계 방향으로 주어진다(벽을 따라 걸을 때 방 내부가 오른쪽에 있다). 모든 벽의 길이의 합은 $300000$을 넘지 않는다.

첫째 줄에 설치할 수 있는 총과 감지기 쌍의 최대 개수 $m$을 출력한다. 이 값은 $n / 2$과 같다.

그다음 $m$개의 줄에 각 쌍을 한 줄에 하나씩 출력한다. 각 줄에는 서로의 광선이 도달하는 두 모서리를 나타내는 두 정수 $a$와 $b$ ($1 \le a < b \le n$)를 공백 하나로 구분해 출력하며, 레이저 총은 모서리 $a$(더 작은 번호)에, 대응하는 감지기는 모서리 $b$에 둔다. 쌍은 $a$가 증가하는 순서로 나열한다. 짝짓기가 유일하고 각 모서리가 정확히 한 쌍에만 속하므로 이 출력은 유일하게 정해진다.

이 그림은 함정에 레이저 총과 감지기를 배치하는 하나의 최적 예를 보여 준다.