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 i-th 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 56 12 13 23 34 45 35 2 23 24 00 Sample Output 0 1