As you may know, Mr. Ed is a very important international businessman. He owns many data centers all around the world, where he keep critical files for his international operations. More specifically, Mr. Ed owns n data centers, numbered from 1 to n. Among these data centers, there are network connections that allow both endpoints of the connection to transfer files with a bandwidth of 50 GB. To ensure complete access to his files, the data centers are connected in such a way that, for any pair (a, b) of distinct data centers, there is at least one way of reaching b from a. This global network is so powerful that transferring a file along any connection takes no time. Anyway, Mr. Ed knows that the transmission time is no problem in his network, the real problem occurs when he tries to move a file that exceeds the bandwidth of a connection. Explicitly, Mr. Ed cannot transfer instantly a file of 100 GB along a single connection in the network; he will need to transfer one half of the file in one instant and the other half in another instant of time. Fortunately, data centers can segment a file in multiple parts in order to distribute the transfer load among multiple paths. That way, one file of 100 GB may be transferred instantly. Notice that there might be no way of segmenting a file to achieve this all the time. Figure 1. One way of segmenting a file to transfer it from data center 1 to 4 instantly (left). There is no way to instantly transfer a file of 100 GB from 1 to 4 (right). To ensure that always is possible to instantly transfer a file of 100 GB between data centers, Mr. Ed can increase (by 1 GB) the bandwidth of any connection by paying 1 dollar. Mr. Ed do not like to pay for more than he requires, so he asked you to write a software that, given the description of his n data centers and the network connections between them, answers several queries of the type: which is the minimum number of dollars I need to pay in order to assure that I can instantly transfer a file of 100 GB from data center u to data center v? Input The input will contain several test cases. The first line of each test case contains 2 integers n and m (1 ≤ n ≤ 10, 000 and 1 ≤ m ≤ 20, 000): the number of data centers and the number of connections. The next m lines contains 2 integers a and b each (1 ≤ a, b ≤ n), representing that there is a network connection between data center a and data center b. The will be no connections from any data center to itself and there will be at most one connection between any two data centers. The next line contains 1 integer q (1 ≤ q ≤ 20,000): the number of queries you need to answer. Following this, there will be q lines with 2 integers u and v each (1 ≤ u, v ≤ n), representing the source data center and target data center for the q queries. Test cases end with a blank line. The last test case is followed by a single line containing 2 zeroes.
2/2 Output For each test case, print the case number followed by q lines with the answer to every query on the test case. Print a single blank line between cases (see format below). Note: The example test cases show the networks illustrated in figure 1. Test case number 1 is the network shown in the left and the second shows the example network in the right. Sample Input 45 12 24 13 34 14 2 14 32 43 12 13 14 2 14 32 00 Sample Output Case #1: 0 0 Case #2: 50 100