SP18393 IE5 - Hamiltonian Cycles

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** (N test cases follow. The first line of each test case contains two integers, **n** (k (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.