
ZOJ Problem Set  2841
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 nonadjacent 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 HINT 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 