Server Time: Sun Sep 24, 2017 1:55 pm
Welcome ( logout
1279 - Graph Coloring
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

Given an undirected graph G, you want to color each vertex of the graph using K colors. The colors are numbered from 0 to K-1. But there is one restriction. Let v be any vertex of the graph and u1, u2 ... um be the adjacent vertices of v, then

color(v) = color(u1) + color(u2) + ... + color(um) (modulo K)

Now you have to find the number of ways you can color the graph maintaining this restriction.


Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing three integers N, M and K (1 ≤ N ≤ 100, 2 ≤ K ≤ 109 and K is a prime) where N denotes the number of vertices and M denotes the number of edges of the graph. Each of the next M lines contains two integers u v (1 ≤ u, v ≤ N, u ≠ v) denoting that there is an edge between vertex u and v. You can safely assume that there is at most one edge between any two vertices.


For each case, print the case number and the result modulo 1000000007.

Sample Input

Output for Sample Input


6 0 5

5 4 3

1 2

1 3

2 4

3 5

Case 1: 1

Case 2: 3


For the second case, let the colors be red (0), green (1) and blue (2). Then the possible results are:


Problem Setter: Manzurur Rahman Khan
Special Thanks: Jane Alam Jan (Description, Solution, Dataset)
Developed and Maintained by
Copyright © 2012
LightOJ, Jane Alam Jan