Historia OI -> XII OI 2004/2005 -> Zadania

SIO

MAIN

Zadanie: Kości

Gra w kości jest grą dwuosobową, w pełni losową. W ostatnim czasie zdobywa ona w Bajtocji rosnącą popularność. W stolicy tego kraju istnieje nawet specjalny klub dla jej wielbicieli. Bywalcy klubu przyjemnie spędzają czas rozmawiając ze sobą i od czasu do czasu rozgrywają partyjkę swojej ulubionej gry z losowo napotkanym graczem. Osoby, które wygrają najwięcej rozgrywek danego dnia zyskują miano szczęściarza. Zdarza się, że wieczór w klubie upływa w spokojnej atmosferze i rozgrywanych jest niewiele partii. Wtedy nawet jedna wygrana może wystarczyć aby zostać szczęściarzem.

Pewnego razu ten zaszczytny tytuł wywalczył sobie straszny pechowiec Bajtazar. Był on tym tak zaskoczony, że całkowicie zapomniał ile partii wygrał. Zastanawia się teraz, jak wielkie było jego szczęście i czy może pech go wreszcie opuścił. Wie kto z kim i ile partii grał tego wieczora. Nie wie jednak jakie były wyniki. Bajtazar chce wiedzieć jaka najmniejsza liczba wygranych partii mogła dawać tytuł szczęściarza. Pomóż zaspokoić ciekawość Bajtazara!

Zadanie

Napisz program, który:

wczyta ze standardowego wejścia dla każdej rozegranej partii parę uczestniczących w niej graczy,
znajdzie najmniejszą taką liczbę k, że istnieje układ wyników rozgrywek, w którym każdy gracz wygrywa co najwyżej k partii,
wypisze na wyjście liczbę k i wyniki wszystkich partii w znalezionym układzie.

Wejście

W pierwszym wierszu wejścia znajduje się para liczb całkowitych n i m oddzielonych pojedynczym odstępem, 1 <= n <= 10 000, 0 <= m <= 10 000; n oznacza liczbę graczy, a m liczbę rozgrywek. Gracze są ponumerowani od 1 do n. W kolejnych m wierszach znajdują się pary numerów graczy, oddzielone pojedynczym odstępem, opisujące ciąg rozgrywek. Ta sama para może pojawiać się wiele razy w podanym ciągu.

Wyjście

Pierwszy wiersz wyjścia powinien zawierać znalezioną liczbę k. Dla każdej pary numerów graczy a, b podanej w i-tym wierszu wejścia, w i-tym wierszu wyjścia powinna pojawić się liczba 1 gdy gracz o numerze a wygrywa z graczem o numerze b w znalezionym układzie wyników rozgrywek, lub 0 w przeciwnym przypadku.

koszad.eps

Przykład

Dla danych wejściowych:

poprawną odpowiedzią jest:

Wersja do druku