提示: 欢迎访问OurACM平台。
Problem 1874 Tree Game

Accept: 77    Submit: 257
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

As we know, Aekdycoin loves games. Now he is playing a game called “Tree Game”. The roles are following:

1.You will be given an undirected graph (no self-loops, and there are no more than one edges between two vertices).

2.In each turn, you could pick up an edge and delete it from the graph, or you could move an edge form [a,b] to [c,d] (if there is no edge between c and d).

3.After several turns, he may be able to get a Spanning Tree.

In Figure 1, we delete an edge [3,4] In Figure 2, we move the edge from [2,4] to [3,4]. Then we finally get a Spanning Tree.

But as we know, there result Spanning Tree may not be unique! AekdyCoin is not so good at program, so could you write a program to help him to calculate the number of different Spanning Tree AekdyCoin may get? (Because the answer may be huge, you only have to tell AekdyCoin the remainder of the answer after divided by P, P will be given)

Note: If there is at least one different edge between Spanning Tree A and Spanning Tree B, then we say A is different to B.

Input

There are no more than 100 cases For every cases, the first line contains three integers N, M, P (1 <= N <= 16, 0 <= M <= N * (N - 1) / 2, 1<= P <= 10^9) Then M lines. Every contains only two integers a, b, indicates there is an edge between a and b (1 <= a, b <= N) There are no self-loops, and there is at most one edge between two vertices in all cases.

Output

Output one line. First output “Case idx: ”, here idx is the case number count from 1. Then output the remainder of the answer after divided by P.

Sample Input

3 1 10 1 2 3 3 10 1 2 2 3 1 3

Sample Output

Case 1: 0 Case 2: 3

Hint

In case 1, we could find only one valid way to get a Spanning Tree. In case 2, we could find no way to get a Spanning Tree.

Source

AekdyCoin

Submit  Back  Status  Discuss