Autostrady
Limit pamięci: 128 MB
Bajtocja jest niewielkim krajem, w którym znajduje się miast połączonych
dwukierunkowymi drogami. Z każdego miasta można dojechać do każdego innego, z czego
mieszkańcy Bajtocji skrupulatnie korzystają. To powoduje, że bajtockie drogi
są notorycznie zakorkowane. Zbudowano więc dodatkowo pewną liczbę autostrad i
połączono nimi wybrane pary miast.
Przez trasę rozumiemy ciąg kolejnych dróg i/lub autostrad, łączących sąsiednie miasta.
Miasta na trasie nie mogą się powtarzać.
Dla danej pary miast , istnieje dokładnie jedna trasa, która nie korzysta
z żadnej autostrady; nazwiemy ją trasą główną pomiędzy i .
Mieszkańcy, jadąc z miasta do miasta , mogą wybrać czy jadą trasą główną,
czy chcą skorzystać z pewnej autostrady. W tym drugim przypadku ich trasa nie może
przecinać trasy głównej poza miastami i oraz musi korzystać z dokładnie
jednej autostrady.
Twoim zadaniem jest napisanie programu, który będzie odpowiadał na pytania o liczbę
poprawnych tras pomiędzy danymi parami miast.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita
() oznaczająca liczbę miast w Bajtocji.
Miasta ponumerowane są liczbami całkowitymi od do .
Kolejne wierszy zawiera po dwie liczby całkowite , () oznaczające, że istnieje droga między miastami i .
W kolejnym wierszu znajduje się liczba () oznaczająca
liczbę autostrad, następne wierszy zawiera ich opisy.
W kolejnym wierszu znajduje się liczba () oznaczająca
liczbę zapytań, które opisane są w następnych wierszach.
Zarówno opisy autostrad jak i zapytania są podane w takim samym formacie jak opisy dróg.
Wyjście
Na standardowe wyjście należy wypisać dokładnie wierszy. Wiersz -ty powinien
zawierać odpowiedź na -te zapytanie z wejścia.
Przykład
Dla danych wejściowych:
9
1 2
2 3
4 2
1 5
5 6
7 5
7 8
9 7
4
2 5
3 4
6 4
8 3
4
4 9
2 5
1 6
1 7
poprawną odpowiedzią jest:
1
4
2
2
Autor zadania: Tomasz Idziaszek.