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.