def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getintsm1(): return [int(x)-1 for x in input().split()]
T = int(input())
for caseno in range(T):
    C, L = getints()
    
    for i in range(1, C):
        print(i, i + 1)
    print(C, 1)
    
    remaining = L - C
    start = 1
    while remaining:
        ntodo = min(remaining, C - start - 1, C - 3)
        for i in range(ntodo):
            print(start, start + i + 2)
        remaining -= ntodo
        start += 1
    
    rnb = [[] for _ in range(C)]
    for _ in range(L):
        x,y = getintsm1()
        rnb[x].append(y)
        rnb[y].append(x)
    rdeg = [len(x) for x in rnb]
    rmd = min(rdeg)
    rlow = [x <= rmd + 1 for x in rdeg]
    rnr = [([x for x in rnb[i] if rlow[x]] if rlow[i] else []) for i in range(C)]
    
    temp = [(len(rnr[i]) if rlow[i] else C) for i in range(C)]
    temp1 = min(temp)
    curr = next(i for i in range(C) if temp[i] == temp1)
    ring = [curr]
    used = {curr}
    while True:
        temp = [x for x in rnr[curr] if x not in used]
        if not temp: break
        curr = temp[0]
        ring.append(curr)
        used.add(curr)
    
    ring += [i for i in range(C) if rmd + 1 < rdeg[i] < C]
    ring += [i for i in range(C) if rdeg[i] == C]
    
    last = ring[-1]
    for i in ring:
        print(last + 1, i + 1)
        last = i