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.