You are given an acyclic, bidirectional graph with nodes and M edges. The nodes are numbered from 1 to . You are given queries.
Query: Given colors, the colors are numbered fron 1 to , you have to find the number of ways for coloring the graph by maintaining the following rules.
First line contains (), number of nodes and (), number of edges.
Next lines contain two different integers and (), an edge between and .
Next line contains (), number of queries.
Next lines contain an integer (), number of colors.
For each query, print the number of ways for coloring the graph. You have to print the mod value with .
Input | Output |
---|---|
3 2 1 2 1 3 2 2 3 | 2 12 |