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ś.