Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3013 Accepted Submission(s): 587 Problem Description 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. Input 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 Output For each RTQ prints a line containing a single integer representing the number of crossings which the driver MUST pass. Sample Input 5 6 1 2 1 3 2 3 3 4 4 5 3 5 2 2 3 2 4 0 0 Sample Output 0 1