Małpki
Limit pamięci: 32 MB
Na drzewie wisi małpek ponumerowanych od 1 do . 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 i , , . Liczba oznacza liczbę małpek, a liczba czas (w sekundach) przez jaki obserwujemy małpki. Kolejne wierszy zawiera opis sytuacji początkowej. W wierszu () znajdują się dwie liczby całkowite oznaczające numery małpek trzymanych przez małpkę nr . Pierwsza z tych liczb to numer małpki trzymanej lewą łapką, a druga - prawą. Liczba oznacza, że małpka ma wolną łapkę. Kolejne wierszy opisuje wyniki obserwacji małpek. W -tym spośród tych wierszy () 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 .
Wyjście
Twój program powinien wypisać na standardowe wyjście dokładnie liczb całkowitych, po jednej w wierszu. Liczba w wierszu powinna oznaczać chwilę, w której małpka nr spadła na ziemię, lub być równa , 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
poprawną odpowiedzią jest:
-1 1 1
Autor zadania: Andrzej Gąsienica-Samek.