In order to count the monsters from another dimension, many stars in galaxy joint the Association Counter Monsters (ACM). They built many bidirectional tunnels to exchange messages. They built some tunnels so that any circle in the graph formed by the tunnel network, whose length is larger than 3, had at least one chord. A chord is an edge connecting two non-adjacent points in the cycle.
One day, the Chief of ACM asked you to draw a map of the stars in ACM. In the map, the two endpoint of any tunnel must have different colors. For security reason, the more methods of drawing the map, the better. So the Chief asked you how many methods there were if he provided you n colors.
Given you all the tunnels among the stars, your task is to answer the Chief's question as soon as possible.
Input
The input contains several test cases.
For each case, the first line contains two integers n (2 <= n <= 1000), m, indicating the number of stars in ACM and the number of tunnels. The following m lines contain two integers each, indicating the stars that tunnel connects. The stars are numbered from 1 to n. No tunnel connects a star to itself, and no two stars are connected with more than one tunnel. Then an integer P (0 < P <= 1000), the number of the Chief's questions, follows. The following P lines contain 2 integers C (0 < C <= 1000000000), M (0 < M <= 1000000000), each, meaning that the Chief provides you C colors, and that you should output the number of methods module M.
Output
For each quest, output the answer in one line.
Sample Input
4 5
1 2
2 3
3 4
4 1
1 3
2
2 10
3 10
Sample Output
0
6
