from argparse import ArgumentParser
import random

parser = ArgumentParser(description="Create a random tree and a cycle, possibly connected")

parser.add_argument("-n", type=int)
parser.add_argument("--connected", action="store_true")
parser.add_argument("--seed", type=int, default=0)

args = parser.parse_args()
random.seed(args.seed)
n = args.n

# random tree on nodes 1..n//2

edges: list[tuple[int, int]] = []
for u in range(2, n//2 + 1):
    v = random.randrange(1, u)
    edges.append((v,u))

# cycle on nodes n//2 + 1 .. n
cycle_edges = list(zip(range(n//2 + 1, n), range(n//2 + 2, n + 1))) + [(n//2 + 1, n)]
edges.extend(cycle_edges)

# possibly add edge from some tree node to n//2 + 1
if args.connected:
    edges.append((random.randrange(n//2+1), n//2 + 1))

print(n, len(edges))
for u, v in edges:
    print(u,v)