Vista 3

어느 날 프라하의 한 대기업이 모든 컴퓨터에 새 운영체제를 설치하기로 했다. 이 운영체제는 미국의 다른 대기업이 만들었다. 마지막 컴퓨터에 설치하자 나머지 컴퓨터가 모두 멈춰서 원격으로 제어할 수 없게 되었다. 관리자는 각 컴퓨터를 직접 찾아가 수동으로 재부팅해야 하므로, 모든 컴퓨터를 방문하는 경로가 필요하다.

각 컴퓨터는 평면 위의 점 $(x, y)$이고, 두 컴퓨터 사이의 거리는 유클리드 거리 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$이다.

첫 줄에 컴퓨터의 수 $N$ ($1 \le N \le 1000000$)이 주어진다. 이어지는 $N$개의 줄에는 $i$번째 컴퓨터의 좌표 $x_i$, $y_i$ ($0 \le x_i, y_i \le 1000000$)가 정수로 주어진다. 모든 컴퓨터는 서로 다른 위치에 있다.

컴퓨터 번호를 방문 순서대로 $N+1$개의 줄에 출력한다. 마지막 번호는 첫 번호와 같아야 하며, 경로는 시작한 컴퓨터로 돌아와야 한다. 시작 컴퓨터는 아무거나 골라도 된다.