Vista 8

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

관리자가 방문할 컴퓨터의 순서를 정해 주자. 시작한 컴퓨터로 돌아와야 한다(그곳에서 다시 재부팅을 시작하지 않기를 바란다). 각 컴퓨터의 위치는 좌표 (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개의 줄로 이루어지며, 추천하는 방문 순서대로 컴퓨터의 번호를 담는다. 마지막 컴퓨터는 첫 번째 컴퓨터와 같아야 한다. 순회는 어느 컴퓨터에서든 시작할 수 있다.