weekly contest 1

#### Start

2019-09-14 01:00 AKDT

## weekly contest 1

#### End

2019-09-15 01:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -334 days 15:21:40

24:00:00

0:00:00

# Problem ICycles (Easy)

Note that this is an easier version of the problem cycleshard.

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.

## Input

The first line of input gives the number of cases, $T$. $T$ test cases follow. The first line of each test case contains two integers, $n$ and $k$. 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.

You may assume that $1 \leq T \leq 10$, $0 \leq k \leq 15$ and $3 \leq n \leq 10$.

## Output

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.

Sample Input 1 Sample Output 1
2
4 1
1 2
8 4
1 2
2 3
4 5
5 6

Case #1: 1
Case #2: 660