Mrówki i biedronka
Limit pamięci: 32 MB
Jak wiadomo, mrówki potrafią "hodować" mszyce. Mszyce wydzielają słodką rosę miodową, którą spijają mrówki. Mrówki zaś bronią mszyc przed ich największymi wrogami - biedronkami.
Na drzewie obok mrowiska znajduje się właśnie taka hodowla mszyc. Mszyce żerują na liściach oraz w rozgałęzieniach drzewa. W niektórych z tych miejsc znajdują się również mrówki patrolujące drzewo. Dla ustalenia uwagi, mrówki są ponumerowane od jeden w górę. Hodowli zagraża biedronka, która zawsze siada na drzewie tam, gdzie są mszyce, czyli na liściach lub w rozgałęzieniach. W chwili, gdy gdzieś na drzewie usiądzie biedronka, mrówki patrolujące drzewo ruszają w jej stronę, aby ją przegonić. Kierują się przy tym następującymi zasadami:
- z każdego miejsca na drzewie (liścia lub rozgałęzienia) można dojść do każdego innego miejsca (bez zawracania) tylko na jeden sposób; każda mrówka wybiera właśnie taką drogę do miejsca lądowania biedronki,
- jeżeli w miejscu lądowania biedronki znajduje się mrówka, biedronka natychmiast odlatuje,
- jeżeli na drodze, od aktualnego położenia mrówki do miejsca lądowania biedronki, znajdzie się inna mrówka, to ta położona dalej od biedronki kończy wędrówkę i zostaje w miejscu swojego aktualnego położenia,
- jeżeli dwie lub więcej mrówek próbuje wejść na to samo rozgałęzienie drzewa, to robi to tylko jedna mrówka - ta z najmniejszym numerem, a reszta mrówek pozostaje na swoich miejscach (liściach lub rozgałęzieniach),
- mrówka, która dociera do miejsca lądowania biedronki, przegania ją i pozostaje w tym miejscu.
Dla uproszczenia przyjmujemy, że przejście gałązki łączącej liść z rozgałęzieniem lub łączącej dwa rozgałęzienia, zajmuje wszystkim mrówkom jednostkę czasu.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis drzewa, początkowe położenia mrówek oraz miejsca, w których kolejno siada biedronka,
- dla każdej mrówki znajdzie jej końcowe położenie i wyznaczy liczbę mówiącą, ile razy przegoniła ona biedronkę.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna
liczba całkowita , równa łącznej liczbie liści i rozgałęzień w drzewie,
.
Przyjmujemy, że liście i rozgałęzienia są ponumerowane od 1 do
.
W kolejnych
wierszach są opisane gałązki - w każdym z tych
wierszy są zapisane dwie liczby całkowite
i
oznaczające,
że dana gałązka łączy miejsca
i
.
Gałązki pozwalają na przejście z każdego miejsca na drzewie, do
każdego innego miejsca.
W
-szym wierszu jest zapisana jedna liczba całkowita
,
i
, równa liczbie mrówek patrolujących drzewo.
W każdym z kolejnych
wierszy zapisana jest jedna liczba całkowita
z przedziału od 1 do
.
Liczba zapisana w wierszu
oznacza początkowe położenie
mrówki nr
.
W każdym miejscu (liściu lub rozgałęzieniu) może znajdować się co
najwyżej jedna mrówka.
W wierszu
zapisana jest jedna liczba całkowita
,
,
mówiąca ile razy biedronka siada na drzewie.
W każdym z kolejnych
wierszy zapisana jest jedna liczba całkowita
z zakresu od 1 do
.
Liczby te opisują kolejne miejsca, w których siada biedronka.
Wyjście
Twój program powinien wypisać na standardowe wyjście wierszy.
W
-tym wierszu powinny zostać
zapisane dwie liczby całkowite oddzielone pojedynczym odstępem -
końcowa pozycja
-tej mrówki (numer rozgałęzienia lub liścia) i
liczba mówiąca, ile razy przegoniła ona biedronkę.
Przykład
Dla danych wejściowych:
4 1 2 1 3 2 4 2 1 2 2 2 4
poprawną odpowiedzią jest:
1 0 4 2
Autor zadania: Krzysztof Loryś.