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.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;

/*
@author : sanskarXrawat
@date   : 10/17/2021
@time   : 4:56 PM
 */
@SuppressWarnings("ALL")
public class B {


    public static void main(String[] args) throws Throwable {
        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);
            Solution solver = new Solution ();
            solver.solve (1, in, out);
            in.close ();
            out.close ();
        }
    }

    @SuppressWarnings("unused")
    static class Solution {
        static final Debug debug = new Debug (true);

        public void solve(int testNumber, FastInput in, FastOutput out) {

            int test=in.ri ();
            while(test-->0){
                int n=in.ri (),m=in.ri ();
                //n is size of tree;
                //m is restrictions
                ArrayList<Integer>[] g=new ArrayList[n+1];
                for (int i = 0; i <n; i++) {
                    g[i+1]=new ArrayList<> ();
                }
                ArrayList<Integer> B=new ArrayList<> ();

                for (int i = 0; i <m; i++) {
                    int a=in.ri (),b=in.ri (),c=in.ri ();
                    g[a].add (c);
                    g[c].add (a);
                    g[a].add (b);
                    g[b].add (a);
                }
//                StringBuilder sb=new StringBuilder ();
                int counter=0;


                outer:for (int i = 0; i <=n-1; i++) {

                    for (int j = 0; j <g[i+1].size (); j++) {

                        if(counter==n){
                            break outer;
                        }
//                        sb.append ((i+1)+" "+g[i+1].get (j)).append ("\n");
                        out.prtl ((i+1)+" "+g[i+1].get (j));
                        counter++;
                    }
                }

//                out.prtl(sb.toString ());
            }

        }


    }


    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private final StringBuilder cache = new StringBuilder (THRESHOLD * 2);
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;

        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(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this (new OutputStreamWriter (os));
        }

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

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

        public FastOutput println(String c) {
            return append (c).println ();
        }

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

        final <T> void prt(T a) {
            append (a + " ");
        }

        final <T> void prtl(T a) {
            append (a + "\n");
        }

        public FastOutput flush() {
            try {
                os.append (cache);
                os.flush ();
                cache.setLength (0);
            } catch (IOException e) {
                throw new UncheckedIOException (e);
            }
            return this;
        }

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

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

        public FastOutput printf(String format, Object... args) {
            return append (String.format (format, args));
        }

        private static int countDigits(long l) {
            if (l >= 1000000000000000000L) return 19;
            if (l >= 100000000000000000L) return 18;
            if (l >= 10000000000000000L) return 17;
            if (l >= 1000000000000000L) return 16;
            if (l >= 100000000000000L) return 15;
            if (l >= 10000000000000L) return 14;
            if (l >= 1000000000000L) return 13;
            if (l >= 100000000000L) return 12;
            if (l >= 10000000000L) return 11;
            if (l >= 1000000000L) return 10;
            if (l >= 100000000L) return 9;
            if (l >= 10000000L) return 8;
            if (l >= 1000000L) return 7;
            if (l >= 100000L) return 6;
            if (l >= 10000L) return 5;
            if (l >= 1000L) return 4;
            if (l >= 100L) return 3;
            if (l >= 10L) return 2;
            return 1;
        }

        private static int countDigits(int l) {
            if (l >= 1000000000) return 10;
            if (l >= 100000000) return 9;
            if (l >= 10000000) return 8;
            if (l >= 1000000) return 7;
            if (l >= 100000) return 6;
            if (l >= 10000) return 5;
            if (l >= 1000) return 4;
            if (l >= 100) return 3;
            if (l >= 10) return 2;
            return 1;
        }

    }


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

        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 long readLong() {
            boolean rev = false;

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

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

            return rev ? val : -val;
        }

        public long rl() {
            return readLong ();
        }

        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);
        }

        public int rs(char[] data, int offset) {
            return readString (data, offset);
        }

        public char[] rsc() {
            return readString ().toCharArray ();
        }

        public int rs(char[] data) {
            return rs (data, 0);
        }

        public int readString(char[] data, int offset) {
            skipBlank ();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (char) next;
                next = read ();
            }

            return offset - originalOffset;
        }

        public char rc() {
            return readChar ();
        }

        public char readChar() {
            skipBlank ();
            char c = (char) next;
            next = read ();
            return c;
        }

        public double rd() {
            return nextDouble ();
        }

        public double nextDouble() {
            int c = read ();
            while (isSpaceChar (c))
                c = read ();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read ();
            }
            double res = 0;
            while (!isSpaceChar (c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow (10, readInt ());
                if (c < '0' || c > '9')
                    throw new InputMismatchException ();
                res *= 10;
                res += c - '0';
                c = read ();
            }
            if (c == '.') {
                c = read ();
                double m = 1;
                while (!isSpaceChar (c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow (10, readInt ());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException ();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read ();
                }
            }
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar (c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }

        public final int readByteUnsafe() {
            if (ptr < bufLen) return buf[ptr++];
            ptr = 0;
            try {
                bufLen = is.read (buf);
                if (bufLen > 0) {
                    return buf[ptr++];
                } else {
                    return -1;
                }
            } catch (IOException e) {
                throw new UncheckedIOException (e);
            }
        }

        public final int readByte() {
            if (ptr < bufLen) return buf[ptr++];
            ptr = 0;
            try {
                bufLen = is.read (buf);
                if (bufLen > 0) {
                    return buf[ptr++];
                } else {
                    throw new java.io.EOFException ();
                }
            } catch (IOException e) {
                throw new UncheckedIOException (e);
            }
        }

        public final String nextLine() {
            tokenBuf.clear ();
            for (int b = readByte (); b != '\n'; b = readByteUnsafe ()) {
                if (b == -1) break;
                tokenBuf.append (b);
            }
            return new String (tokenBuf.getRawBuf (), 0, tokenBuf.size ());
        }

        public final String nl() {
            return nextLine ();
        }

        public final boolean hasNext() {
            for (int b = readByteUnsafe (); b <= 32 || b >= 127; b = readByteUnsafe ()) {
                if (b == -1) return false;
            }
            --ptr;
            return true;
        }

        public void readArray(Object T) {
            if (T instanceof int[]) {
                int[] arr = (int[]) T;
                for (int i = 0; i < arr.length; i++) {
                    arr[i] = ri ();
                }
            }
            if (T instanceof long[]) {
                long[] arr = (long[]) T;
                for (int i = 0; i < arr.length; i++) {
                    arr[i] = rl ();
                }
            }
            if (T instanceof double[]) {
                double[] arr = (double[]) T;
                for (int i = 0; i < arr.length; i++) {
                    arr[i] = rd ();
                }
            }
            if (T instanceof char[]) {
                char[] arr = (char[]) T;
                for (int i = 0; i < arr.length; i++) {
                    arr[i] = readChar ();
                }
            }
            if (T instanceof String[]) {
                String[] arr = (String[]) T;
                for (int i = 0; i < arr.length; i++) {
                    arr[i] = next ();
                }
            }
            if (T instanceof int[][]) {
                int[][] arr = (int[][]) T;
                for (int i = 0; i < arr.length; i++) {
                    for (int j = 0; j < arr[0].length; j++) {
                        arr[i][j] = ri ();
                    }
                }
            }
            if (T instanceof char[][]) {
                char[][] arr = (char[][]) T;
                for (int i = 0; i < arr.length; i++) {
                    for (int j = 0; j < arr[0].length; j++) {
                        arr[i][j] = readChar ();
                    }
                }
            }
            if (T instanceof long[][]) {
                long[][] arr = (long[][]) T;
                for (int i = 0; i < arr.length; i++) {
                    for (int j = 0; j < arr[0].length; j++) {
                        arr[i][j] = rl ();
                    }
                }

            }
        }

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


        private static final class ByteBuffer {
            private static final int DEFAULT_BUF_SIZE = 1 << 12;
            private byte[] buf;
            private int ptr = 0;

            private ByteBuffer(int capacity) {
                this.buf = new byte[capacity];
            }

            private ByteBuffer() {
                this (DEFAULT_BUF_SIZE);
            }

            private ByteBuffer append(int b) {
                if (ptr == buf.length) {
                    int newLength = buf.length << 1;
                    byte[] newBuf = new byte[newLength];
                    System.arraycopy (buf, 0, newBuf, 0, buf.length);
                    buf = newBuf;
                }
                buf[ptr++] = (byte) b;
                return this;
            }

            private char[] toCharArray() {
                char[] chs = new char[ptr];
                for (int i = 0; i < ptr; i++) {
                    chs[i] = (char) buf[i];
                }
                return chs;
            }

            private byte[] getRawBuf() {
                return buf;
            }

            private int size() {
                return ptr;
            }

            private void clear() {
                ptr = 0;
            }
        }


    }


    static class Debug {
        private final boolean offline;
        private final PrintStream out = System.err;
        static int[] empty = new int[0];

        public Debug(boolean enable) {
            offline = enable && System.getSecurityManager () == null;
        }

        public Debug debug(String name, Object x) {
            return debug (name, x, empty);
        }

        public Debug debug(String name, long x) {
            if (offline) {
                debug (name, "" + x);
            }
            return this;
        }

        public Debug debug(String name, String x) {
            if (offline) {
                out.printf ("%s=%s", name, x);
                out.println ();
            }
            return this;
        }

        public Debug debug(String name, Object x, int... indexes) {
            if (offline) {
                if (x == null || !x.getClass ().isArray ()) {
                    out.append (name);
                    for (int i : indexes) {
                        out.printf ("[%d]", i);
                    }
                    out.append ("=").append ("" + x);
                    out.println ();
                } else {
                    indexes = Arrays.copyOf (indexes, indexes.length + 1);
                    if (x instanceof byte[]) {
                        byte[] arr = (byte[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug (name, arr[i], indexes);
                        }
                    } else if (x instanceof short[]) {
                        short[] arr = (short[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug (name, arr[i], indexes);
                        }
                    } else if (x instanceof boolean[]) {
                        boolean[] arr = (boolean[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug (name, arr[i], indexes);
                        }
                    } else if (x instanceof char[]) {
                        char[] arr = (char[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug (name, arr[i], indexes);
                        }
                    } else if (x instanceof int[]) {
                        int[] arr = (int[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug (name, arr[i], indexes);
                        }
                    } else if (x instanceof float[]) {
                        float[] arr = (float[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug (name, arr[i], indexes);
                        }
                    } else if (x instanceof double[]) {
                        double[] arr = (double[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug (name, arr[i], indexes);
                        }
                    } else if (x instanceof long[]) {
                        long[] arr = (long[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug (name, arr[i], indexes);
                        }
                    } else {
                        Object[] arr = (Object[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug (name, arr[i], indexes);
                        }
                    }
                }
            }
            return this;
        }

    }
}