import sys
import random


def create_network(C, L):
    max_pow2 = 1
    while max_pow2 <= C:
        max_pow2 *= 2
    max_pow2 //= 2
    edges = []
    for i in range(1, C + 1):
        k = 1
        while k <= max_pow2:
            j = (i + k - 1) % C + 1
            if i < j:
                edges.append((i, j))
            k *= 2
    extra_edges = []
    for i in range(C):
        j = (i + 2) % C
        if j == i - 1:
            j = (j + 1) % C
        extra_edges.append((i+1, j+1))
    random.shuffle(extra_edges)
    for i in range(L - len(edges)):
        edges.append(extra_edges[i])
    assert len(edges) == L
    return edges


def solve(C, L):
    edges = create_network(C, L)
    print("\n".join(f"{u} {v}" for u, v in edges))
    sys.stdout.flush()
    perm_edges = []
    for _ in range(L):
        u, v = map(int, input().split())
        perm_edges.append((u, v))
    adj = [[] for _ in range(C + 1)]
    for i, j in perm_edges:
        adj[i].append(j)
        adj[j].append(i)
    visited = [False] * (C + 1)
    path = []

    def dfs(u, p):
        visited[u] = True
        path.append(u)
        for v in adj[u]:
            if v != p:
                if visited[v]:
                    if path[-2] == v:
                        path.append(v)
                        return True
                    continue
                if dfs(v, u):
                    return True
        path.pop()
        visited[u] = False
        return False

    for u in range(1, C + 1):
        if not visited[u]:
            dfs(u, -1)