Vista 9

프라하에 있는 이름 없는 대기업 하나가 모든 컴퓨터에 새 운영체제(미국의 또 다른 이름 없는 대기업이 만든)를 설치하기로 했다. 그 운영체제를 만든 회사가 아주 유명했고 광고도 많았으니, 모두들 이 운영체제가 최고일 거라며 들떠 있었다. 그러나 주 네트워크 관리자만은 그렇게 기뻐하지 않았다. 그의 우려는 곧 현실이 되었다. 마지막 컴퓨터에 새 운영체제를 설치하는 동안 나머지 컴퓨터가 모두 멈춰 버려 원격으로 제어할 수 없게 된 것이다. 이제 불쌍한 관리자는 각 컴퓨터를 직접 찾아가 손으로 재시작하는 것 외에 다른 방법이 없다.

이 관리자를 도와, 그가 컴퓨터를 방문하고 처음 출발한 컴퓨터로 돌아오는 순서를 추천해 주자. (그 컴퓨터에서 다시 재부팅을 시작하지 않기를 바란다.) 각 컴퓨터의 위치는 두 좌표 (x), (y)로 주어진다. 모든 컴퓨터는 평면 위에 있고, 두 컴퓨터 사이의 거리는 유클리드 거리로 정의한다. 즉 좌표 ((x_1), (y_1))인 컴퓨터와 ((x_2), (y_2))인 컴퓨터 사이의 거리는 (\sqrt{(x_1-x_2)^2+(y_1-y_2)^2})이다.

첫째 줄에 정수 (N) (1 ≤ (N) ≤ 1 000 000)이 주어지며, 이는 컴퓨터의 수이다. 이어서 (N)개의 줄이 주어지고, (i)번째 줄에는 두 정수 (x_i), (y_i) (0 ≤ (x_i), (y_i) ≤ 1 000 000)가 주어지며, 이는 (i)번째 컴퓨터의 좌표이다. 컴퓨터는 모두 서로 다른 위치에 있다.

출력은 (N) + 1개의 줄로 이루어지며, 추천하는 이동 순서대로 컴퓨터의 번호를 출력한다. 마지막 컴퓨터는 첫 번째 컴퓨터와 같아야 한다. 순회는 어느 컴퓨터에서 시작해도 된다.