题目描述
City C is really a nightmare of all drivers for its traffic jams. To solve the traffic problem, the mayor plans to build a RTQS (Real Time Query System) to monitor all traffic situations. City C is made up of N crossings and M roads, and each road connects two crossings. All roads are bidirectional. One of the important tasks of RTQS is to answer some queries about route-choice problem. Specifically, the task is to find the crossings which a driver MUST pass when he is driving from one given road to another given road.
输入
There are multiple test cases.
For each test case:
The first line contains two integers N and M, representing the number of the crossings and roads.
The next M lines describe the roads. In those M lines, the ith line (i starts from 1)contains two integers Xi and Yi, representing that roadi connects crossing Xi and Yi (Xi≠Yi).
The following line contains a single integer Q, representing the number of RTQs.
Then Q lines follows, each describing a RTQ by two integers S and T(S≠T) meaning that a driver is now driving on the roads and he wants to reach roadt . It will be always at least one way from roads to roadt.
The input ends with a line of “0 0”.
Please note that: 0 < N <= 10000, 0 < M <= 100000, 0 < Q <= 10000, 0 < Xi, Yi <= N, 0 < S,T <= M
输出
For each RTQ prints a line containing a single integer representing the number of crossings which the driver MUST pass.
5 6
1 2
1 3
2 3
3 4
4 5
3 5
2
2 3
2 4
0 0