import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    c, l = map(int, input().split())

    l0 = l

    out = []

    out.append(f'1 {c}')
    for i in range(c - 1):
        out.append(f'{i + 1} {i + 2}')

    l -= c

    for j in range(1, c + 1):
        for i in range(j - 2, 0, -1):
            if i == 1 and j == c:
                continue
            if l == 0:
                continue

            out.append(f'{i} {j}')
            l -= 1

    assert l == 0

    assert len(out) == l0
    print('\n'.join(out))
    sys.stdout.flush()

    adj = [[] for _ in range(c)]
    deg = [0] * c
    for _ in range(l0):
        u, v = map(int, input().split()); u -= 1; v -= 1
        adj[u].append(v)
        adj[v].append(u)

        deg[u] += 1
        deg[v] += 1

    assert min(deg) >= 2

    #print(deg)
    
    if max(deg) == 2:
        assert l0 == c
        
        vis = [False] * c
        st = [0]

        order = []
        while st:
            u = st.pop()

            if vis[u]:
                continue

            vis[u] = True
            order.append(u)

            for v in adj[u]:
                st.append(v)
        assert all(vis)
    elif l0 == c + 1:
        vis = [False] * c
        st = [0]

        order = []
        while st:
            u = st.pop()

            if vis[u]:
                continue

            vis[u] = True
            order.append(u)

            for v in adj[u]:
                if deg[u] == 2 or deg[v] == 2:
                    st.append(v)
        assert all(vis)
    elif 2 in deg:
        base = -1

        for i in range(c):
            if deg[i] == 2:
                continue

            for v in adj[i]:
                if deg[v] == 2:
                    base = i

        vis = [False] * c
        st = [base]

        order = []
        while st:
            u = st.pop()

            if vis[u]:
                continue

            vis[u] = True
            order.append(u)

            for v in adj[u]:
                if deg[v] == 2 or deg[u] == 2:
                    st.append(v)

        if deg[order[0]] < deg[order[-1]]:
            order = order[::-1]

        assert not all(vis)

        for u in adj[order[-1]]:
            if not vis[u]:
                order.append(u)
                vis[u] = True
                break
        else:
            assert False

        #Rest should be complete
        for i in range(c):
            if not vis[i]:
                order.append(i)        
    else:
        md = min(deg)
        for i in range(c):
            if deg[i] == md:
                base = i

        order = [adj[base].pop(), base, adj[base].pop()]
        vis = [False] * c
        for v in order:
            vis[v] = True

        #Rest should be complete
        for i in range(c):
            if not vis[i]:
                order.append(i)

    assert len(order) == c
    print(' '.join(map(lambda x: str(x + 1), order)))
    sys.stdout.flush()