W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.
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.
Na standardowe wyjście należy wypisać dokładnie wierszy. Wiersz -ty powinien zawierać odpowiedź na -te zapytanie z wejścia.
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.