Polish version    English version  
  Historia OI -> XII OI 2004/2005 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodników
Przydatne zasoby
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 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