Bridges

In the two-dimensional kingdom of the Flatlanders, every important place sits at a point of the form $(X, 0)$, where $X$ is a positive integer.

The king has ordered $N$ pairs of important places to be joined by bridges. A bridge between $(A, 0)$ and $(B, 0)$ (with $A < B$) is a polyline made of three segments: from $(A, 0)$ to $(A, P)$, then from $(A, P)$ to $(B, P)$, then from $(B, P)$ to $(B, 0)$, where the positive integer $P$ is called the level of the bridge. The $N$ bridges must all have different levels, and those levels are exactly the integers from $1$ to $N$.

Bridges may cross one another, but every crossing is technically inconvenient. Assign a level to each bridge so that the total number of points where two bridges cross is as small as possible. Because all vertical segments have distinct $x$-coordinates and all horizontal segments have distinct heights, two bridges can only cross where the vertical part of one meets the horizontal part of the other. Each place appears in the list of pairs at most once.

The first line contains one integer $Z$ ($Z = 1$), the number of test cases. The test cases follow.

Each test case begins with a line containing one integer $N$ ($1 \le N \le 5000$), the number of pairs of places to connect. Each of the next $N$ lines contains two integers $A$ and $B$ ($1 \le A < B \le 2N$), meaning the places at $(A, 0)$ and $(B, 0)$ must be joined by a bridge. Since every place is listed at most once, the $2N$ coordinates are exactly the integers from $1$ to $2N$.

For each test case, print one line. List the bridge numbers in increasing order of their assigned levels, separated by single spaces: first the bridge placed at level $1$, then the bridge at level $2$, and so on up to level $N$. Bridges are numbered by their order in the input, starting from $1$.

The assignment must minimize the total number of crossings. If several assignments reach that minimum, print the lexicographically smallest sequence: the one whose bridge number at level $1$ is as small as possible, then, among those, whose bridge number at level $2$ is as small as possible, and so on.

Write $(x_1, x_2, \ldots, x_N)$ for the assignment that puts bridge $x_i$ at level $i$.

In the first test case, both $(2, 3, 1)$ and $(3, 2, 1)$ produce $0$ crossings, which is clearly the smallest possible. Of the two, $(2, 3, 1)$ is lexicographically smaller, so it is the answer.