Lotniska

Limit pamięci: 32 MB

W państwie X istnieją lotniska w miastach. Znane są maksymalne przepustowości tych lotnisk — lotnisko w mieście może mieć co najwyżej połączeń lotniczych z innymi miastami. Należy zaplanować sieć połączeń lotniczych między tymi miastami w taki sposób, by miasto miało dokładnie połączeń z innymi miastami, przy czym zakładamy, że każde połączenie jest dwukierunkowe i każde miasto może mieć z innym tylko jedno połączenie.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia liczbę miast oraz liczby ,
• układa sieć połączeń lotniczych, taką że dla każdego od do miasto ma dokładnie połączeń z innymi miastami,
• zapisuje na standardowe wyjście listę wszystkich tworzących sieć połączeń.

Dane są tak dobrane, by rozwiązanie zadania istniało. Jeśli zadanie ma wiele rozwiązań, Twój program powinien znajdować tylko jedno. Może się zdarzyć, że podróż z jednego miasta do drugiego, nawet z przesiadkami, nie jest możliwa.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana liczba całkowita spełniająca nierówność . Jest to liczba miast. W kolejnych wierszach są zapisane liczby całkowite dodatnie , po jednej w każdym wierszu.

Wyjście

Na standardowe wyjście należy zapisać wszystkie połączenia lotnicze sieci utworzonej przez Twój program. Każde połączenie należy zapisać w osobnym wierszu w postaci dwóch liczb całkowitych dodatnich oddzielonych pojedynczym odstępem, tj. numerów dwóch połączonych miast. Numery miast w wierszu mogą występować w dowolnej kolejności; również kolejność zapisywania połączeń w pliku jest dowolna.

Przykład

Dla danych wejściowych:

6
2
3
2
4
1
2

poprawną odpowiedzią jest:

5 4
4 2
1 2
2 3
6 3
4 6
4 1

Autor zadania: Wojciech Guzicki.