Polish version    English version  
  O olimpiadzie -> Zadania


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 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:
4 4
1 2
1 3
1 4
1 2
poprawną odpowiedzią jest:
1
0
0
0
1



Wersja do druku