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.