8798번 - Mosty 다국어

W dwuwymiarowym królestwie Płaszczaków wszystkie ważne miejsca znajdują się w punktach postaci (X,0), gdzie X jest dodatnią liczbą całkowitą.

Niedawno król zarządził połączenie mostami N par ważnych miejsc. Most między punktami (A,0) i (B,0) to łamana składająca się z trzech odcinków: (A,0)-(A,P), (A,P)-(B,P), (B,P)-(B,0), gdzie P jest pewną dodatnią liczbą całkowitą nazywaną poziomem mostu. Wszystkie mosty muszą mieć różne poziomy będące liczbami od 1 do N. 

Mosty mogą się przecinać, ale jest to sytuacja kłopotliwa technicznie. Jak przyporządkować poziomy do poszczególnych mostów, aby zminimalizować liczbę przecięć? Każde miejsce występuje na liście par co najwyżej raz.

W pierwszej linii znajduje się jedna liczba naturalna Z ( Z = 1 ) oznaczająca liczbę zestawów testowych. W kolejnych liniach opisywane są kolejne zestawy.

W pierwszej linii zestawu znajduje się jedna liczba naturalna N ( 1 <= N <= 5 000 ) oznaczająca liczbę par miejsc, które trzeba połączyć mostami. W kolejnych N liniach znajdują się po dwie liczby całkowite A i B ( 1 <= A < B <= 2N ) oznaczające, że miejsca o współrzędnych (A,0), (B,0) należy połączyć mostem.

W jednej linii należy wypisać, pooddzielane spacjami, numery kolejnych mostów posortowanych rosnąco według ich poziomów ( pierwszy ma być numer mostu o najmniejszym poziomie itd. ), minimalizujące liczbę przecięć. Numery mostów odpowiadają kolejności podanej na wejściu. W przypadku istnienia wielu rozwiązań minimalizujących liczbę przecięć należy podać leksykograficznie najmniejsze ( a więc to które minimalizuje numer mostu na poziomie 1, pośród tych rozwiązań to które minimalizuje numer mostu poziomie 2 itd., por. przykład ).

(x₁,x₂,x₃) oznacza ustawienie z mostem nr x_i na poziomie i.

W przypadku ustawień (2,3,1) oraz (3,2,1) liczba przecięć mostów jest równa 0 i jest oczywiście najmniejsza z możliwych. Spośród tych ustawień najmniejsze leksykograficznie jest ustawienie (2,3,1).