Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2841
Galaxy War

Time Limit: 5 Seconds      Memory Limit: 32768 KB

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.


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.


For each quest, output the answer in one line.

Sample Input

4 5
1 2
2 3
3 4
4 1
1 3
2 10
3 10

Sample Output



The graph with the property mentioned above is called chordal graph. A permutation s = [v1 , v2 ,..., vn] of the vertices of such graph is called a perfect elimination order if each vi is a simplicial vertex of the subgraph of G induced by { vi ,..., vn}. A vertex is called simplicial if its adjacency set induces a complete subgraph, that is, a clique (not necessarily maximal). The perfect elimination order of a chordal graph can be computed with the following codes:

procedure maximum cardinality search(G, s) 
    for all vertices v of G do 
        set label[v] to zero 
    end for 
    for all i from n downto 1 do 
        choose an unnumbered vertex v with largest label 
        set s(v) to i{number vertex v} 
        for all unnumbered vertices w adjacent to vertex v do 
            increment label[w] by one 
        end for 
    end for 
end procedure

Author: GUAN, Yao
Source: Zhejiang University Local Contest 2007
Submit    Status