Note that this is a harder version of the problem
cycleseasy.
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
selfedges and no repeated edges.
You may assume that $1 \leq T
\leq 10$, $0 \leq k \leq
15$ and $3 \leq n \leq
300$.
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
