In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Byteland is a small country, with cities connected by bidirectional roads. From each city there is just one way of reaching every other city using the road network, which causes severe traffic jams. For this reason several highways have been built; each highway connects some pair of cities.
By a route we mean a sequence of roads and/or highways. All cities on a route should be distinct. For each pair of cities , there exists exactly one route which does not use any highway; we call such a route the main route between and .
People going from a city to a city can either choose the main route or use some highway. In the latter case the route cannot intersect the main route except for the cities and and must contain exactly one highway.
Your task is to calculate the number of routes people can take between given pairs of cities.
The first line of input contains a single integer () - the number of cities in Byteland. Cities are numbered from to . Each of the next lines contains two integers , () meaning that cities and are connected by a road.
The next line contains an integer () - the number of highways. Each of the next lines contains a description of a single highway. The next line contains an integer () - the number of queries. Each of the next lines contains a description of a query. Both highways and queries are given in the same format as the roads.
Your program should output exactly lines. The -th line should contain the number of routes in the -th query.
For the input data:
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
the correct result is:
1 4 2 2
Task author: Tomasz Idziaszek.