Lord Omkar would like to have a tree with n nodes (3 ≤ n ≤ 10^5) and has asked his disciples to construct the tree. However, Lord Omkar has created m (1 ≤ m < n) restrictions to ensure that the tree will be as heavenly as possible. 

A tree with n nodes is an connected undirected graph with n nodes and n-1 edges. Note that for any two nodes, there is exactly one simple path between them, where a simple path is a path between two nodes that does not contain any node more than once.

Here is an example of a tree: 

<image>

A restriction consists of 3 pairwise distinct integers, a, b, and c (1 ≤ a,b,c ≤ n). It signifies that node b cannot lie on the simple path between node a and node c. 

Can you help Lord Omkar and become his most trusted disciple? You will need to find heavenly trees for multiple sets of restrictions. It can be shown that a heavenly tree will always exist for any set of restrictions under the given constraints.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^4). Description of the test cases follows.

The first line of each test case contains two integers, n and m (3 ≤ n ≤ 10^5, 1 ≤ m < n), representing the size of the tree and the number of restrictions.

The i-th of the next m lines contains three integers a_i, b_i, c_i (1 ≤ a_i, b_i, c_i ≤ n, a, b, c are distinct), signifying that node b_i cannot lie on the simple path between nodes a_i and c_i. 

It is guaranteed that the sum of n across all test cases will not exceed 10^5.

Output

For each test case, output n-1 lines representing the n-1 edges in the tree. On each line, output two integers u and v (1 ≤ u, v ≤ n, u ≠ v) signifying that there is an edge between nodes u and v. Given edges have to form a tree that satisfies Omkar's restrictions.

Example

Input


2
7 4
1 2 3
3 4 5
5 6 7
6 5 4
5 3
1 2 3
2 3 4
3 4 5


Output


1 2
1 3
3 5
3 4
2 7
7 6
5 1
1 3
3 2
2 4

Note

The output of the first sample case corresponds to the following tree: 

<image> For the first restriction, the simple path between 1 and 3 is 1, 3, which doesn't contain 2. The simple path between 3 and 5 is 3, 5, which doesn't contain 4. The simple path between 5 and 7 is 5, 3, 1, 2, 7, which doesn't contain 6. The simple path between 6 and 4 is 6, 7, 2, 1, 3, 4, which doesn't contain 5. Thus, this tree meets all of the restrictions.

The output of the second sample case corresponds to the following tree: 

<image>
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.IOException;
import java.lang.reflect.Field;
import java.nio.charset.StandardCharsets;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            BOmkarAndHeavenlyTree solver = new BOmkarAndHeavenlyTree();
            int testCount = Integer.parseInt(in.next());
            for (int i = 1; i <= testCount; i++)
                solver.solve(i, in, out);
            out.close();
        }
    }

    static class BOmkarAndHeavenlyTree {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            int m = in.ri();
            boolean[] occur = new boolean[n];
            for (int i = 0; i < m; i++) {
                int a = in.ri() - 1;
                int b = in.ri() - 1;
                int c = in.ri() - 1;
                occur[b] = true;
            }
            int firstNotOccur = -1;
            for (int i = 0; i < m; i++) {
                if (!occur[i]) {
                    firstNotOccur = i;
                    break;
                }
            }
            for (int i = 0; i < n; i++) {
                if (i == firstNotOccur) {
                    continue;
                }
                out.append(firstNotOccur + 1).append(' ').append(i + 1).println();
            }
        }

    }

    static class FastInput {
        private final InputStream is;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public String next() {
            return readString();
        }

        public int ri() {
            return readInt();
        }

        public int readInt() {
            boolean rev = false;

            skipBlank();
            if (next == '+' || next == '-') {
                rev = next == '-';
                next = read();
            }

            int val = 0;
            while (next >= '0' && next <= '9') {
                val = val * 10 - next + '0';
                next = read();
            }

            return rev ? val : -val;
        }

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private OutputStream writer;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);
        private static Field stringBuilderValueField;
        private char[] charBuf = new char[THRESHOLD * 2];
        private byte[] byteBuf = new byte[THRESHOLD * 2];

        static {
            try {
                stringBuilderValueField = StringBuilder.class.getSuperclass().getDeclaredField("value");
                stringBuilderValueField.setAccessible(true);
            } catch (Exception e) {
                stringBuilderValueField = null;
            }
            stringBuilderValueField = null;
        }

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(OutputStream writer) {
            this.writer = writer;
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println() {
            return append('\n');
        }

        public FastOutput flush() {
            try {
                if (stringBuilderValueField != null) {
                    try {
                        byte[] value = (byte[]) stringBuilderValueField.get(cache);
                        writer.write(value, 0, cache.length());
                    } catch (Exception e) {
                        stringBuilderValueField = null;
                    }
                }
                if (stringBuilderValueField == null) {
                    int n = cache.length();
                    if (n > byteBuf.length) {
                        //slow
                        writer.write(cache.toString().getBytes(StandardCharsets.UTF_8));
//                writer.append(cache);
                    } else {
                        cache.getChars(0, n, charBuf, 0);
                        for (int i = 0; i < n; i++) {
                            byteBuf[i] = (byte) charBuf[i];
                        }
                        writer.write(byteBuf, 0, n);
                    }
                }
                writer.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                writer.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }
}

