문제
알고리즘 캠프가 끝나면 빌린 강의실을 정리해야 한다.
강의실을 정리하기 위해서는 우선 강의실에 배치한 책상들을 전부 옮겨야 한다.
하지만, 무작정 옮겼다가는 책상 위에 있는 많은 짐들이 거슬린다. 따라서 사람들은 책상을 옮길 때 차근차근 조심해서 옮겨야 한다.
또, 이동 거리가 길수록 짐들이 사라질 가 능성이 많으므로, 아래 그림과 같이 y축 방향으로 아래쪽으로 움직인다.
이 때 책상이 돌아가는 경우는 없다.
책상을 옮길 때, 책상을 옮기는 경로 상에 다른 책상이 있으면 안 된다.
이때 책상의 양 끝이 닿는 것 도 안 된다.
책상을 x축 아래로 옮겼으면, 짐을 모두 옮기고 책상은 기자재 본부로 반납한다.
당신은 N개의 책상을 문제 없이 옮길 수 있게 책상을 옮기는 순서를 정해야 한다.
N개의 책상의 정 보가 주어졌을 때 책상을 옮기는 순서를 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 N이 주어진다. (1 ≤ N ≤ 5,000)
두 번째 줄부터 N개의 줄에는 1번 책상부터 N번 책상에 대해서 각 책상의 양 끝 점의 x, y좌표가 주 어진다.
모든 좌푯값은 0 이상 10,000 이하이다.
출력
첫 번째 줄에 옮겨야 할 책상의 번호를 먼저 옮기는 순서대로 출력한다.
답이 여러 개이면 그중 가장 먼저 옮기는 책상의 번호가 가장 작은 것을 출력한다.
그래도 답이 여러 개이면 그 중 2번째로 옮기는 책 상의 번호가 가장 작은 것을 출력한다.
이런 식으로 반복하여 가장 앞선 답을 출력한다.
예제1
입력
4
1322
1132
2473
3353
출력
2143
예제2
입력
4
0011
1203
2233
4031
출력
1243
예제3
입력
3
4655
21151
3287
출력
231
출처
COCI 2015/2016 contest2 3