Wyznaczanie planu sieci drogowej

Limit pamięci: 64 MB

Bajtazar wybiera się w podróż samochodową po Bajtocji, lecz niestety ma problemy z nabyciem mapy tego kraju. Od znajomych dowiedział się o pewnych właściwościach bajtockiej sieci dróg:

• W Bajtocji jest miast, ponumerowanych od do .
• Każda droga jest dwukierunkowa i łączy ze sobą pewne dwa różne miasta.
• Każde dwa różne miasta są połączone dokładnie jedną trasą, złożoną z jednej bądź większej liczby dróg, na której żadne miasto się nie powtarza.
• Najdłuższa z tras, na której żadne miasto się nie powtarza, składa się z dróg.

Na podstawie zdobytych informacji Bajtazar zamierza spróbować odtworzyć mapę drogową Bajtocji. Teoretycznie możliwych planów sieci drogowej, spełniających podane kryteria, może być dosyć dużo, więc Bajtazarowi wystarczy dowolny poprawny plan.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczby oraz ,
• wyznaczy dowolny plan sieci drogowej, zgodny z informacjami zdobytymi przez Bajtazara, lub stwierdzi, że żaden taki plan nie istnieje,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy i jedyny wiersz wejścia zawiera dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem.

Wyjście

Jeżeli nie istnieje żaden plan sieci drogowej, odpowiadający wartościom parametrów oraz , to pierwszy i jedyny wiersz wyjścia powinien zawierać jedno słowo BRAK. W przeciwnym przypadku wyjście powinno składać się z wierszy. Każdy wiersz powinien zawierać opis jednej dwukierunkowej drogi - dwie różne liczby całkowite z zakresu od do , oddzielone pojedynczym odstępem i oznaczające numery miast połączonych daną drogą. Kolejność wypisania dróg i numerów miast połączonych drogami może być dowolna.

Przykład

Dla danych wejściowych:

6 3

poprawną odpowiedzią jest:

1 3
2 3
3 4
4 5
4 6

Autor zadania: Jakub Radoszewski.