Vista 2

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

불쌍한 관리자를 도와 컴퓨터를 방문하고 출발했던 컴퓨터로 돌아오는 순서를 추천해 주자(그곳에서 또 한 차례 재부팅을 시작하지 않기를 바라면서). 각 컴퓨터의 위치는 두 좌표 (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개의 줄로 이루어진다. 마지막 컴퓨터는 첫 번째 컴퓨터와 같아야 한다. 순회는 어느 컴퓨터에서든 시작할 수 있다.