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.