from argparse import ArgumentParser
import random

parser = ArgumentParser(
    description="Create random tadpole graphs and their unions; tadpoles are merged at their leaf (or anywhere if they're cycles"
)

parser.add_argument("-n", type=int)
parser.add_argument("--lo", type=int, help="lower bound on the cycle/clique size")
parser.add_argument("--hi", type=int, help="upper bound on the cycle/clique size")
parser.add_argument("--chords", action="store_true")
parser.add_argument("--tadpoles", type=int, default=1, help="the number of tadpoles")
parser.add_argument("--seed", type=int, default=0)

args = parser.parse_args()
random.seed(args.seed)
n = args.n
if args.hi is None:
    args.hi = n


def tadpole(u, v, s, chords=False):
    """Create tadpole starting from u, using the vertices in u..v and with cycle size s.
       If chords==True, also add "stripes" across the tadpole's body (so as to produce
       many vertices of degree > 2 to allow many digon-free walks.
    """
    assert s >= 3
    assert v - s + 1 > u
    w = v - s + 1  # the degree-3 vertex, which cannot be u itself
    edges = list(zip(range(u, w), range(u + 1, w + 1)))  # the stick; can be empty
    edges.extend(zip(range(w, w + s), range(w + 1, w + s)))
    edges.append((v, w))
    if chords:
        uu, vv = w + 1, w + s - 2
        while uu < vv - 1:
            edges.append((uu, vv))
            uu += 1
            vv -= 1
    return edges


edges: list[tuple[int, int]] = []

k = args.tadpoles


def random_partition(total, parts, lo=4):
    if parts < 1:
        raise ValueError("parts must be at least 1")

    min_required = parts * lo
    if total < min_required:
        raise ValueError(
            f"total must be at least {min_required} to satisfy the minimum value {lo} per part"
        )

    if parts == 1:
        return [total]

    remaining = total - min_required

    # Stars and bars: choose (parts - 1) cut points from (remaining + parts - 1) positions
    cuts = sorted(random.sample(range(1, remaining + parts), parts - 1))
    full_cuts = [0] + cuts + [remaining + parts]
    raw_parts = [full_cuts[i + 1] - full_cuts[i] - 1 for i in range(parts)]

    result = [p + lo for p in raw_parts]
    assert sum(result) == total, f"Sum mismatch: expected {total}, got {sum(result)}"
    return result


result = random_partition(n - 1, k)

edges = []
tadpole_start = 2
for i in range(args.tadpoles):
    edges.append((1, tadpole_start))
    tadpole_edges = tadpole(
        tadpole_start,
        tadpole_start + result[i] - 1,
        random.randrange(3, min(result[i], args.hi + 1)),
        chords=args.chords
    )
    tadpole_start += result[i]
    edges.extend(tadpole_edges)

print(n, len(edges))
for u, v in edges:
    print(*sorted([u, v]))