Ewakuacja

Limit pamięci: 64 MB

Bajtocka Republika Bitowa organizuje przyszłoroczne finały Mistrzostw Świata w Piłce Bitowej. W przygotowaniach bierze udział Bajtazar, który odpowiada za opracowanie planu ewakuacji ze stadionu w każdym mieście, w którym rozgrywane będą mecze. Najwięcej problemów sprawia mu plan ewakuacji dla Bajtogrodu, bo co rusz dostaje informacje o ulicach, które będą zamknięte w trakcie trwania finałów, i musi poprawiać wcześniejsze ustalenia. Co jakiś czas dostaje pytania od działaczy z Bajtockiego Związku Piłki Bitowej. Chcą oni wiedzieć jak szybko można się ewakuować ze stadionu do wskazanego skrzyżowania w mieście.

W Bajtogrodzie jest skrzyżowań połączonych jednokierunkowymi ulicami. Ewakuacja musi przebiegać zgodnie z kierunkiem ulic. Przebycie każdej ulicy łączącej dwa skrzyżowania zajmuje dokładnie jedną minutę.

Napisz program, który pomoże Bajtazarowi w pracy. Dla podanych informacji o zamknięciach ulic powinien on obliczać odpowiedzi na pytania działaczy.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite , i (, ) oznaczające kolejno liczbę skrzyżowań w Bajtogrodzie, liczbę łączących je ulic oraz liczbę zapytań. Skrzyżowania są ponumerowane liczbami od do . Stadion znajduje się przy skrzyżowaniu numer . Każdy z kolejnych wierszy zawiera opis jednej ulicy w postaci dwóch liczb całkowitych , (), które oznaczają, że z do prowadzi jednokierunkowa ulica, której przebycie zajmuje jedną minutę. Pomiędzy parą skrzyżowań będzie co najwyżej jedna ulica w każdym kierunku.

W kolejnych wierszach znajdują się opisy zapytań w kolejności chronologicznej. Opis jednego zapytania składa się ze znaku () oraz liczby całkowitej .

Zapytanie rozpoczynające się od opisuje informację o zamknięciu ulicy. Liczba zawiera się wówczas w przedziale i oznacza numer zamkniętej ulicy. Ulice numerujemy zgodnie z kolejnością na wejściu.

Zapytanie rozpoczynające się od oznacza pytanie o możliwość ewakuacji do skrzyżowania numer (w tym przypadku ). Możesz założyć, że co najmniej jedno zapytanie na wejściu będzie typu E.

Wyjście

Należy wypisać po jednym wierszu dla każdego zapytania typu E, w kolejności zgodnej z tą na wejściu. Odpowiedzią dla jednego zapytania jest najkrótszy czas potrzebny na dotarcie ze stadionu do skrzyżowania numer , korzystając jedynie z ulic, które nie zostały wcześniej zamknięte. Jeśli dotarcie do skrzyżowania jest niemożliwe, należy wypisać .

Przykład

Dla danych wejściowych:

7 8 8
1 2
1 3
1 5
2 4
3 1
3 5
4 5
4 6
E 7
E 5
U 7
E 6
E 5
U 2
E 5
E 4

poprawną odpowiedzią jest:

-1
1
3
1
1
2

Autor zadania: Jakub Łącki.