시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 0 0 0 0.000%

문제

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 ( 1 <= N <= 5 000 ) oznaczająca liczbę par miejsc, które trzeba połączyć mostami. W kolejnych 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 ).

예제 입력 1

1
3
1 6
2 3
4 5

예제 출력 1

2 3 1

힌트

(x1,x2,x3) oznacza ustawienie z mostem nr xi 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).