Vista 6

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

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