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.