Mosty

05.01.2011
Trudność

Mosty

Limit czasowy: 2000 milisekund
Limit pamięciowy: 32000 kilobajtów


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.

Wejście

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.

Wyjście

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 ).

Przykład

Wejście Wyjście
1
3
1 6
2 3
4 5

2 3 1

Wyjaśnienie przykładu

(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).

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
4.166665
Twoja ocena: Brak Ocena: 4.2 (12 ocen)

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com