import sys

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

        # Build string with all pairs
        pairs = []
        for i in range(c):
            a = i + 1
            b = (i + l//c) % c + 1
            pairs.append(f"{a} {b}")
        print('\n'.join(pairs))
        sys.stdout.flush()

        # Build dictionary of edges
        edges = {}
        for _ in range(l):
            u, v = map(int, input().split())
            if u not in edges:
                edges[u] = set()
            if v not in edges:
                edges[v] = set()
            edges[u].add(v)
            edges[v].add(u)

        # Build ring using dictionary of edges and set for ring
        ring = {pairs[0].split()[0]}
        while len(ring) < c:
            for u in edges[ring[-1]]:
                if u not in ring:
                    ring.add(u)
                    break
        print(' '.join(ring))
        sys.stdout.flush()

if __name__ == '__main__':
    main()