체계적인 외판원

외판원이 한 번의 여행에서 방문해야 하는 도시 목록을 받았다. 그는 각 도시를 적어도 한 번 방문하기만 하면 아무 도시에서나 출발하고 아무 도시에서나 끝낼 수 있다. 출발 도시와 도착 도시가 같을 필요는 없다.

다른 외판원들은 최적 경로를 짜고 찾는 데 너무 많은 시간을 쓴다. 이 외판원은 대신 더 체계적인 방법을 택했다.

그는 먼저 모든 도시를 왼쪽 절반과 오른쪽 절반으로 나눈다. 도시 수가 홀수이면 오른쪽 절반에 도시가 하나 더 들어간다. 그다음 두 절반 중 하나를 고르고, 고른 절반의 도시를 모두 방문한 뒤에 다른 절반으로 넘어간다.

고른 절반의 도시를 방문하려면 이 도시 집합을 아래쪽 절반과 위쪽 절반으로 나눈다. 집합의 도시 수가 홀수이면 위쪽 절반에 도시가 하나 더 들어간다. 여기서도 한쪽 절반의 도시를 모두 방문한 뒤에 다른 쪽으로 간다.

가로 방향 나누기와 세로 방향 나누기를 번갈아 적용하여 완전한 경로가 나올 때까지 이 과정을 이어간다. 이 방식으로 얻을 수 있는 경로 중에서 모든 도시를 방문하는 가장 짧은 경로를 구하라.

첫째 줄에 도시의 수 $N$이 주어진다. 이어서 $N$개의 줄에 각 도시의 평면 좌표를 나타내는 정수 $X_i$와 $Y_i$가 공백으로 구분되어 주어진다. 모든 $X_i$ 값은 서로 다르고, 모든 $Y_i$ 값도 서로 다르다.

첫째 줄에 경로의 최소 길이를 출력한다. 공식 해와의 차이가 $10^{-4}$ 이하이면 정답으로 인정한다. 둘째 줄에는 방문 순서대로 도시 번호를 공백으로 구분하여 출력한다. 도시 번호는 입력 순서에 따라 $1$부터 $N$까지이다. 최적 경로가 여럿이면 그중 아무것이나 출력해도 된다.

$1 ≤ N ≤ 1000$

$0 ≤ X_i, Y_i ≤ 10^6$

외판원은 먼저 왼쪽 절반(도시 $1$, $3$, $4$)을 방문하고, 그다음 오른쪽 절반(도시 $2$, $5$, $6$)을 방문한다.

도시 $1$, $3$, $4$를 방문하려면 먼저 위쪽 절반(도시 $3$, $4$)을 방문하고 아래쪽 절반(도시 $1$)을 나중에 방문한다. 위쪽 절반에서는 왼쪽 절반(도시 $3$)을 먼저 가고 오른쪽 절반(도시 $4$)을 나중에 간다.

도시 $2$, $5$, $6$은 아래쪽 절반(도시 $6$)과 위쪽 절반(도시 $2$, $5$)으로 나뉜다. 아래쪽 절반을 먼저 방문한다. 위쪽 절반에서는 오른쪽 절반(도시 $5$)을 먼저 방문하고 왼쪽 절반(도시 $2$)으로 마무리한다.