import sys

def output(s):
    print(s)
    sys.stdout.flush()
    
def Mindegree(L):
    n = max(a for pair in L for a in pair)
    D = {i:[] for i in range(1,n+1)}
    for (a,b) in L:
        D[a].append(b)
        D[b].append(a)

    ring = [min(D, key=lambda v: len(D[v]))]
    used = set(ring)

    while len(ring) < n:
        neighbors = set(D[ring[-1]]) - set(used)
        if not neighbors:
            print(L, n, len(L))
            print(ring)
            crash

        nbr = min(neighbors, key=lambda v: len(D[v]))
        ring.append(nbr)
        used.add(nbr)
    return ring

def Silly(n, links):
    L = [(i,i+1) for i in range(1,n)] + [(n,1)]

    if len(L) == links: return L
    for a in range(n,0,-1):
        for b in range(a-2,0,-1):
            if (a,b) != (n,1):
                L.append((a,b))
                if len(L) == links: return L

T = int(input())
for _ in range(T):
    n, links = map(int, input().split())
    for (a,b) in Silly(n,links):
        print(f"{a} {b}")
    sys.stdout.flush()
    graph = []
    for i in range(links):
        graph.append(list(map(int, input().split())))
    ring = Mindegree(graph)
    print(" ".join(map(str, ring)))
    sys.stdout.flush()