from argparse import ArgumentParser
import random

parser = ArgumentParser(
    description="""
    Create multitadpole graphs (P_k joined with r many C_4 and a single C_3 at a single vertex.
    """
)

parser.add_argument("-k", type=int, help="length of the path (in vertices)")
parser.add_argument("--c4", type=int, help="number of c4s")
parser.add_argument("--shuffle", action="store_true", default=0)
parser.add_argument("--seed", type=int, default=0)

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

n = args.k + 2 + 3 * args.c4
m = args.k - 1 + 3 + 4 * args.c4

print(n, m)
edges = []
for u in range(1, args.k):
    edges.append((u, u+1))

# the high-degree vertex is k
k = args.k

# add args.c4 many C4s at k
for i in range(args.c4):
    u = k + i * 3 + 1
    v = u+1
    w = u+2
    edges.extend([(k, u), (u, v), (v, w), (k, w)])

# add a single C3 at k

u = k + 3 * args.c4 + 1
v = u + 1
edges.extend([(k, u), (u, v), (k, v)])

pi = list(range(1,n+1))
if args.shuffle:
    random.shuffle(pi)

for u, v in edges:
    x, y = pi[u-1], pi[v-1]
    print(min(x, y), max(x, y))