from random import shuffle

def generate_network(C, L):
    links = []
    for i in range(1, C):
        links.append((i, i+1))
    links.append((C, 1))
    extra_links = L - C + 1
    for i in range(1, C-2, 2):
        if extra_links == 0:
            break
        links.append((i, i+2))
        extra_links -= 1
    if C % 2 == 0:
        links.append((C-1, 1))
    for i in range(2, C-2, 2):
        if extra_links == 0:
            break
        links.append((i, i+2))
        extra_links -= 1
    return links

def main():
    T = int(input())
    for t in range(T):
        C, L = map(int, input().split())
        network = generate_network(C, L)
        print('\n'.join(f'{a} {b}' for a, b in network))
        permuted_network = []
        for i in range(L):
            u, v = map(int, input().split())
            permuted_network.append((u, v))
        shuffle(permuted_network)
        new_ids = {i+1: p+1 for i, p in enumerate(sorted(set(u for u, v in permuted_network)))}
        permuted_network.sort(key=lambda x: (new_ids[x[0]], new_ids[x[1]]))
        ids = []
        for i in range(1, C+1):
            ids.append(new_ids[i])
        print(' '.join(str(x) for x in ids))

if __name__ == '__main__':
    main()