2482. Cycles

单点时限: 2.0 sec

内存限制: 256 MB

You are given a complete undirected graph with n nodes numbered from 1 to n. You are also given k forbidden edges in this graph.

You are asked to find the number of Hamiltonian cycles in this graph that don’t use any of the given k edges. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A cycle that contains the same edges is only counted once. For example, cycles 1 2 3 4 1 and 1 4 3 2 1 and 2 3 4 1 2 are all the same, but 1 3 2 4 1 is different.

输入格式

The first line of input gives the number of cases, N(1 ≤ N ≤ 10). N test cases follow. The first line of each test case contains two integers, n(3 ≤ n ≤ 300) and k(0 ≤ k ≤ 15). The next k lines contain two integers each, representing the vertices of a forbidden edge. There will be no self-edges and no repeated edges.

输出格式

For each test case, output one line containing “Case #X: Y”, where X is the case number (starting from 1) and Y is the number of Hamiltonian cycles that do not include any of those k edges. Print your answer modulo 9901.

样例

Input
2
4 1
1 2
8 4
1 2
2 3
4 5
5 6
Output
Case #1: 1
Case #2: 660
Hint:
In the first sample input, there is only one cycle: 1 3 2 4 1.

0 人解决,1 人已尝试。

0 份提交通过,共有 1 份提交。

9.9 EMB 奖励。

创建: 15 年,3 月前.

修改: 6 年,9 月前.

最后提交: 3 年,6 月前.

来源: GCJ 2008

题目标签