Przedziały

Limit pamięci: 32 MB

Dany jest ciąg przedziałów domkniętych , gdzie . Suma tych przedziałów może być przedstawiona w postaci sumy parami rozłącznych przedziałów domkniętych. Zadanie polega na znalezieniu przedstawienia tej sumy w postaci sumy minimalnej liczby parami rozłącznych przedziałów domkniętych. Przedziały tworzące to przedstawienie należy zapisać w pliku wyjściowym w rosnącej kolejności. Mówimy, że dwa przedziały rozłączne i są ustawione w rosnącej kolejności wtedy i tylko wtedy, gdy .

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis ciągu przedziałów,
• wyznaczy parami rozłączne przedziały spełniające warunki zadania,
• wypisze wyznaczone przedziały w rosnącej kolejności na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita , spełniająca nierówność . Jest to liczba przedziałów. W -szym wierszu pliku, , znajduje się opis przedziału w postaci dwóch liczb całkowitych i oddzielonych pojedynczym odstępem, będących odpowiednio jego początkiem i końcem, .

Wyjście

W kolejnych wierszach standardowego wyjścia należy zapisać opisy znalezionych parami rozłącznych przedziałów. W każdym wierszu ma być zapisany opis jednego przedziału w postaci dwóch liczb całkowitych oddzielonych pojedynczym odstępem, będących odpowiednio początkiem i końcem tego przedziału. Przedziały w pliku wyjściowym powinny być zapisane w rosnącej kolejności.

Przykład

Dla danych wejściowych:

5
5 6
1 4
10 10
6 9
8 10

poprawną odpowiedzią jest:

1 4
5 10

Autor zadania: Wojciech Guzicki.