All submissions for this problem are available.
Tommy needs help! Tommy's lost her watch. There are a total of n stations in town and every two are connected via an independant route.Tommy's watch could be at any one of them. Help Tommy check them all and get back? Simple, isn't it? Okay. So, we'll add some rules to how Tommy goes about the task. Firstly, Tommy has money only enough to visit each station once. Secondly, there are routes between selected pairs of stations that Tommy isn't allowed to take. You need to find the total number of routes that Tommy can possibly take.
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 and k. The next k lines contain two integers each, representing the end stations of forbidden route (Route contains only these two stations). 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 paths that do not include any of those k edges. Print your answer modulo 9901.
1 ≤ N ≤ 10,
0 ≤ k ≤ 15.
3 ≤ n ≤ 300
Input 2 4 1 1 2 8 4 1 2 2 3 4 5 5 6 Output Case #1: 1 Case #2: 660 In the first sample input, there is only one path: 1 3 2 4 1.
|Time Limit:||6 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.