-
Notifications
You must be signed in to change notification settings - Fork 6
/
cycleshard.py
43 lines (41 loc) · 1.52 KB
/
cycleshard.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import sys; input = sys.stdin.readline
T = int(input())
MOD = 9901
facts = [1]; twopow = [1]
for i in range(1, 300): facts.append(facts[-1]*i%MOD)
for i in range(16): twopow.append(twopow[-1]*2%MOD)
def dfs(u, p=None):
if not go[0]: return
if vis[u]: go[0] = 0; return cc.append(u)
vis[u] = 1
cc.append(u)
for v in al[u]:
if v != p: dfs(v, u)
# https://stackoverflow.com/questions/4759955/how-do-i-find-the-number-of-hamiltonian-cycles-that-do-not-use-forbidden-edges
for t in range(1, T+1):
ans = 0
n, k = map(int, input().split())
edges = [[*map(lambda x: int(x)-1, input().split())] for _ in range(k)]
for x in range(1<<k):
s = [edges[i] for i in range(k) if (1<<i)&x]
deg = [0]*n; c = 1
for u, v in s: deg[u] += 1; deg[v] += 1
for i in deg:
if i > 2: c = 0; break
if c == 0: continue
sole, cyc, path = [], [], []
al = [[] for _ in range(n)]
for u, v in s: al[u].append(v), al[v].append(u)
vis = [0]*n
for i in range(n):
cc = []
if vis[i] == 0:
go = [1]; dfs(i)
if len(cc) > 1:
if cc[0] == cc[-1]: cyc.append(cc); break
else: path.append(cc)
else: sole.append(cc[0])
if cyc: c = 2*(len(cyc[0]) == n+1)
else: c = twopow[len(path)]*facts[len(path)+len(sole)-1]
ans += c*(-1)**len(s)
print(f'Case #{t}:', ans*4951%MOD) # 1/2 = 4951 mod 9901