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