다리

이차원 평면 왕국에서 모든 중요한 장소는 $(X, 0)$ 꼴의 점에 있으며, 여기서 $X$는 양의 정수입니다.

왕은 중요한 장소 $N$쌍을 다리로 잇도록 명령했습니다. 점 $(A, 0)$과 $(B, 0)$ ($A < B$)을 잇는 다리는 세 개의 선분으로 이루어진 꺾은선입니다. 즉 $(A, 0)$에서 $(A, P)$까지, 이어서 $(A, P)$에서 $(B, P)$까지, 다시 $(B, P)$에서 $(B, 0)$까지이며, 양의 정수 $P$를 그 다리의 높이(level) 라고 부릅니다. $N$개의 다리는 모두 서로 다른 높이를 가져야 하고, 그 높이들은 정확히 $1$부터 $N$까지의 정수입니다.

다리끼리는 서로 교차할 수 있지만, 교차가 생기면 기술적으로 곤란합니다. 두 다리가 만나는 교차점의 총 개수가 최소가 되도록 각 다리에 높이를 배정하세요. 모든 수직 선분의 $x$좌표가 서로 다르고 모든 수평 선분의 높이가 서로 다르므로, 두 다리는 한쪽의 수직 선분이 다른 쪽의 수평 선분과 만나는 곳에서만 교차합니다. 각 장소는 쌍 목록에 최대 한 번만 등장합니다.

첫 번째 줄에 테스트 케이스의 수를 나타내는 정수 $Z$ ($Z = 1$)가 주어집니다. 이어서 테스트 케이스가 주어집니다.

각 테스트 케이스의 첫 줄에는 다리로 이어야 하는 장소 쌍의 수 $N$ ($1 \le N \le 5000$)이 주어집니다. 다음 $N$개의 줄에는 각각 두 정수 $A$와 $B$ ($1 \le A < B \le 2N$)가 주어지며, 이는 $(A, 0)$과 $(B, 0)$의 장소를 다리로 이어야 함을 뜻합니다. 각 장소는 최대 한 번만 등장하므로, $2N$개의 좌표는 정확히 $1$부터 $2N$까지의 정수입니다.

각 테스트 케이스마다 한 줄을 출력합니다. 배정한 높이가 낮은 것부터 순서대로, 각 높이에 놓인 다리의 번호를 공백으로 구분하여 나열합니다. 즉 높이 $1$에 놓인 다리, 높이 $2$에 놓인 다리, 그리고 높이 $N$에 놓인 다리 순서입니다. 다리 번호는 입력에 주어진 순서대로 $1$부터 매깁니다.

배정은 교차점의 총 개수를 최소로 만들어야 합니다. 최소를 달성하는 배정이 여러 개라면 사전순으로 가장 작은 수열을 출력합니다. 즉 높이 $1$의 다리 번호가 가장 작고, 그중에서 높이 $2$의 다리 번호가 가장 작으며, 이런 식으로 이어지는 배정을 선택합니다.

$(x_1, x_2, \ldots, x_N)$은 다리 $x_i$를 높이 $i$에 놓는 배정을 뜻합니다.

첫 번째 테스트 케이스에서 $(2, 3, 1)$과 $(3, 2, 1)$은 모두 교차점이 $0$개이며, 이는 당연히 가능한 최솟값입니다. 이 둘 중 사전순으로 더 작은 것은 $(2, 3, 1)$이므로 이것이 정답입니다.