Server Time: Wed Sep 30, 2020 4:16 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

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.

# Output

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

2

6 0 5

5 4 3

1 2

1 3

2 4

3 5

Case 1: 1

Case 2: 3

# Note

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 JANE ALAM JAN Copyright © 2012 LightOJ, Jane Alam Jan