import sys
input = sys.stdin.readline
print = sys.stdout.write

# function to construct the cycle graph
def construct_graph(C, L):
    k = 1
    while k * (k + 1) // 2 < L:
        k += 1

    edges = []
    for i in range(C):
        for j in range(1, k+1):
            x = i
            y = (i + j) % C
            edges.append((x, y))
    return edges

# function to find the ring in the permuted graph
def find_ring(C, edges):
    graph = [[] for _ in range(C)]
    for x, y in edges:
        graph[x].append(y)
        graph[y].append(x)

    for start in range(C):
        visited = set()
        curr = start
        prev = None
        while True:
            visited.add(curr)
            for neighbor in graph[curr]:
                if neighbor != prev:
                    prev, curr = curr, neighbor
                    break
            else:
                if start in graph[curr]:
                    return [curr] + [x for x in visited if x != curr]

# main function
def main():
    T = int(input())
    for _ in range(T):
        C, L = map(int, input().split())
        edges = construct_graph(C, L)
        for x, y in edges:
            print(f"{x+1} {y+1}\n")
        sys.stdout.flush()

        permuted_edges = [tuple(map(int, input().split())) for _ in range(L)]
        permuted_edges = [(x-1, y-1) for x, y in permuted_edges]

        ring = find_ring(C, permuted_edges)
        print(" ".join(str(x+1) for x in ring) + "\n")
        sys.stdout.flush()

if __name__ == "__main__":
    main()