Megalopolis
Limit pamięci: 32 MB
Globalizacja nie ominęła Bajtocji. Nie ominęła również listonosza Bajtazara, niegdyś chodzącego polnymi drogami pomiędzy wioskami, a dziś pędzącego samochodem po autostradach. Jednak to te dawne spacery Bajtazar wspomina dziś z rozrzewnieniem.
Dawniej bajtockich wiosek, ponumerowanych od
do
, było połączonych dwukierunkowymi polnymi drogami w taki
sposób, że z każdej wioski można było dojść do wioski numer
(zwanej Bitowicami) na dokładnie jeden sposób, w dodatku droga ta
przechodziła jedynie przez wioski o numerach nie większych niż numer
wioski początkowej.
Ponadto każda polna droga łączyła dwie różne wioski i nie
przechodziła przez żadne inne wioski oprócz tych dwóch.
Drogi się nie krzyżowały poza wioskami, lecz mogły istnieć
tunele bądź wiadukty.
Z biegiem czasu kolejne polne drogi zamieniano na autostrady. Bajtazar dokładnie pamięta, kiedy każda z polnych dróg została zamieniona w autostradę. Dziś w Bajtocji nie można już spotkać ani jednej polnej drogi - wszystkie zostały zastąpione autostradami, które połączyły wioski w Bajtockie Megalopolis.
Bajtazar pamięta swoje wyprawy do wiosek z listami. Za każdym razem Bajtazar wyruszał z Bitowic, idąc z listami do pewnej innej wioski. Teraz prosi Cię, żebyś dla każdej takiej wyprawy (która miała miejsce w określonym momencie i prowadziła z Bitowic do określonej wioski) policzył, przez ile polnych dróg ona prowadziła.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia:
- opis dróg, które łączyły kiedyś bajtockie wioski,
- sekwencję zdarzeń: wypraw Bajtazara i momentów gdy poszczególne polne drogi były zamieniane w autostrady,
- dla każdej wyprawy obliczy, iloma polnymi drogami Bajtazar musiał przejść,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna
liczba całkowita (
), oznaczająca
liczbę wiosek w Bajtocji.
W kolejnych
wierszach znajdują się opisy dróg.
Każdy z nich składa się z dwóch liczb całkowitych
,
(
) oddzielonych pojedynczym
odstępem.
Są to numery wiosek połączonych drogą.
W kolejnym wierszu znajduje się jedna liczba
całkowita (
), oznaczająca liczbę wypraw
odbytych przez Bajtazara.
W kolejnych
liniach znajdują się opisy zdarzeń, w
kolejności chronologicznej:
-
Opis postaci A a b (dla
) oznacza, że w danym momencie polną drogę pomiędzy wioskami
oraz
zamieniono na autostradę.
-
Opis postaci W a oznacza, że Bajtazar odbył
wyprawę z Bitowic do wioski numer
.
Wyjście
Na standardowe wyjście Twój program powinien wypisać dokładnie
liczb całkowitych, po jednej w wierszu, oznaczających liczbę
polnych dróg, które pokonał Bajtazar w kolejnych
wyprawach.
Przykład
Dla danych wejściowych:
5 1 2 1 3 1 4 4 5 4 W 5 A 1 4 W 5 A 4 5 W 5 W 2 A 1 2 A 1 3
poprawną odpowiedzią jest:
2 1 0 1
Autor zadania: Szymon Acedański.