**0 人解决**，1 人已尝试。

**0 份提交通过**，共有 1 份提交。

**9.9** EMB 奖励。

**单点时限: **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 奖励。

题目标签