Vista 1

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

관리자가 컴퓨터를 방문하고 처음 출발한 컴퓨터로 돌아오는 순서를 추천해 주자(그곳에서 또 한 번 재부팅을 시작하지 않기를 바란다). 각 컴퓨터의 위치는 두 좌표 (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)번째 줄에는 (i)번째 컴퓨터의 좌표 (x_i), (y_i) (0 ≤ (x_i), (y_i) ≤ 1 000 000)가 주어진다. 컴퓨터들은 서로 다른 위치에 있다.

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