Tivoli

그림은 첫 번째 예제 상황과 최적해 하나를 나타낸다.

리사는 놀이공원에 도착했고, 탈 놀이기구 $N$개를 정했다. 각 놀이기구에는 똑같은 시설이 두 개씩 있어서 시설은 모두 $2N$개다. 리사는 놀이기구마다 한 번씩만 탄다. 모든 시설의 위치가 주어질 때, 리사가 걷는 거리의 합이 가장 짧아지도록 방문할 시설 $N$개와 그 순서를 정하라. 리사는 입구에서 출발해 입구로 돌아와야 한다. 입구는 원점에 있다.

첫 줄에 정수 $N$ ($1 \le N \le 15$)이 주어진다. 이어서 $N$개의 줄이 주어지는데, $i$번째 줄은 놀이기구 $i$를 나타낸다. 각 줄에는 첫 번째 시설의 x좌표와 y좌표, 두 번째 시설의 x좌표와 y좌표, 이렇게 정수 네 개가 있다. 모든 좌표의 절댓값은 100만 미만이다.

같은 위치에 있는 시설은 없으며, 원점에 있는 시설도 없다.

첫 줄에 리사가 걷는 거리를 실수로 출력한다. 이어서 $N$개의 줄에 정수 두 개씩 출력한다. 첫 번째 정수는 리사가 갈 놀이기구 번호($1$ 이상 $N$ 이하)이고, 두 번째 정수는 그 놀이기구에서 이용할 시설 번호($1$ 또는 $2$)다.

최단 거리를 주는 경로가 여럿이면 그중 아무것이나 출력해도 된다. 경로를 거꾸로 돌아도 거리가 같으므로 답은 항상 두 가지 이상이다. 상대 오차 또는 절대 오차는 $10^{-5}$ 미만이어야 한다.