Polish version    English version  
  Historia OI -> X OI 2002/2003 -> 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
XI OI 2003/2004
X OI 2002/2003
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
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
X Olimpiada Informatyczna 2002/2003

Zadanie: mal
Autor: Andrzej Gąsienica-Samek
Małpki

Zawody III stopnia, dzień drugi  
Plik źródłowy: mal.xxx (xxx=pas,c,cpp)

Alternatywne formaty: PostScript | PDF

Na drzewie wisi n małpek ponumerowanych od 1 do n. Małpka z nr 1 trzyma się gałęzi ogonkiem. Pozostałe małpki albo są trzymane przez inne małpki, albo trzymają się innych małpek, albo jedno i drugie równocześnie. Każda małpka ma dwie przednie łapki, każdą może trzymać co najwyżej jedną inną małpkę (za ogon). Rozpoczynając od chwili 0, co sekundę jedna z małpek puszcza jedną łapkę. W ten sposób niektóre małpki spadają na ziemię, gdzie dalej mogą puszczać łapki (czas spadania małpek jest pomijalnie mały).

Zadanie

Napisz program, który:

  • wczyta ze standardowego wejścia opis tego, w jaki sposób małpki się trzymają oraz w jakiej kolejności puszczają łapki,
  • dla każdej małpki obliczy, kiedy spadnie ona na ziemię,
  • wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie dodatnie liczby całkowite n i m, 1 <= n <= 200000, 1 <= m <= 400000. Liczba n oznacza liczbę małpek, a liczba m czas (w sekundach) przez jaki obserwujemy małpki. Kolejne n wierszy zawiera opis sytuacji początkowej. W wierszu k + 1 (1 <= k <= n) znajdują się dwie liczby całkowite oznaczające numery małpek trzymanych przez małpkę nr k. Pierwsza z tych liczb to numer małpki trzymanej lewą łapką, a druga - prawą. Liczba -1 oznacza, że małpka ma wolną łapkę. Kolejne m wierszy opisuje wyniki obserwacji małpek. W i-tym spośród tych wierszy (1 <= i <= m) znajdują się dwie liczby całkowite. Pierwsza z nich oznacza numer małpki, a druga numer łapki (1 - lewa, 2 - prawa), którą małpka puszcza w chwili i - 1.

Wyjście

Twój program powinien wypisać na standardowe wyjście dokładnie n liczb całkowitych, po jednej w wierszu. Liczba w wierszu i powinna oznaczać chwilę, w której małpka nr i spadła na ziemię, lub być równa -1, jeśli małpka nie spadła na ziemię w trakcie obserwacji.

Przykład

Dla danych wejściowych:

3 2
-1 3
3 -1
1 2
1 2
3 1

poprawnym wynikiem jest:

-1
1
1



Wersja do druku