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.*;
    import java.util.*;

    import static java.lang.System.*;
    import static java.lang.Math.*;
    import static java.util.Collections.*;
    import static java.util.Arrays.*;
    public class B {
        public static int swap(int... args) {
            return args[0];
        } static   ArrayList<Integer> primes = new ArrayList<>();
        //static Scanner sc = new Scanner(System.in);
        static FastReader sc = new FastReader();
        public static void main(String[] args) throws IOException {
            do {
                startTime = currentTimeMillis();
                //setOut(new PrintStream("output"));
                //setIn(new FileInputStream("input"));
               int T = sc.nextInt(); while (T-- != 0)
                {
                    solve();

                }
                endTime = currentTimeMillis();
                long duration = endTime - startTime;
                //out.println(duration);
                if (false) {
                    out.println(max(3, 2));
                    Integer[] ARRAY = new Integer[2];
                    ArrayList<Integer> LIST = new ArrayList<>();
                    LIST.add(2);
                    // sort(LIST, reverseOrder());
                    LIST.sort(reverseOrder());
                    sort(ARRAY, reverseOrder());
                    out.println(LIST + " " + Arrays.toString(ARRAY));
                }
            } while (LOCAL);
        }
       static void leftRotate(ArrayList<Integer> arr, int d, int n)
        {
            for (int i = 0; i < d; i++)
                leftRotatebyOne(arr, arr.size());
        }

       static void leftRotatebyOne(ArrayList<Integer> arr, int n)
        {
            int i, temp;
            temp = arr.get(0);
            for (i = 0; i < arr.size() - 1; i++)
                arr.set(i,arr.get(i+1));
            arr.set(n-1,temp);
        }
        static boolean isSorted(Integer arr[], int n)
        {
            if (n == 1 || n == 0)
                return true;
            if (arr[n - 1] < arr[n - 2])
                return false;
            return isSorted(arr, n - 1);
        }
        static int modInverse(int n, int p)
        {
            return (int)power1(n, p - 2, p);
        }

        // Returns nCr % p using Fermat's
        // little theorem.
        static int nCrModPFermat(int n, int r,
                                 int p)
        {

            if (n<r)
                return 0;
            // Base case
            if (r == 0)
                return 1;

            // Fill factorial array so that we
            // can find all factorial of r, n
            // and n-r
            int[] fac = new int[n + 1];
            fac[0] = 1;

            for (int i = 1; i <= n; i++)
                fac[i] = fac[i - 1] * i % p;

            return (fac[n] * modInverse(fac[r], p)
                    % p * modInverse(fac[n - r], p)
                    % p)
                    % p;
        }
        static class Tuple implements Comparable<Tuple>{
           private int a,b,c;

            public Tuple(int a, int b, int c) {
                this.a = a;
                this.b = b;
                this.c = c;
            }

            @Override
            public int compareTo(Tuple o) {
                return 0;
            }
        }
        public static void solve() throws IOException {
    /////////////////////////////////////////////////////////////////////
        int n =sc.nextInt(),m=sc.nextInt();
        ArrayList<Tuple> list = new ArrayList<>();
            boolean [ ] is = new boolean[n+10];
            for (int i = 0; i < m; i++) {
                int a =sc.nextInt(),b=sc.nextInt(),c=sc.nextInt();
                is[b] =true;
                list.add(new Tuple(a,b,c));

            }
            int root = -1;
            for (int i = 1; i <=n; i++) {
                if(!is[i]){
                    root = i;
                    break;
                }
            }
            for (int i = 1; i <=n; i++) {
                if(i!=root){
                    out.println(root+" " + i +" ");
                }
            }


    ///////////////////////////////////////////////////////////////////////

        }

        public static final boolean LOCAL = System.getProperty("ONLINE_JUDGE")==null;
        // public static final boolean LOCAL = System.getProperty("LOCAL")!=null;
        public static final String ANSI_RED = "\u001B[31m";
        public static final String ANSI_RESET = "\u001B[0m";
        static long startTime;
        static long endTime;
        static boolean[] prime;
        static final int M = (int) 1e9 + 7;
        static final long MM = (long) M * M;
        static final int MAX = Integer.MAX_VALUE;
        static final int MIN = Integer.MIN_VALUE;
        static final int SIZE = (int) 1e9 * 2;
        static int [] visited;
        static ArrayList<ArrayList<Integer>> graph;
        static ArrayList<Integer> dfs;
        static  boolean isCyclic = false;
        static void dfs(int src){
            visited[src] = 1;
            for(Integer integer : graph.get(src) ){
                if(visited[integer]!=1){
                    dfs(integer);
                }
            }
            dfs.add(src);

        }
        static void detectCycle(int src){
            visited[src] =2;
            for(Integer integer : graph.get(src)){
                if(visited[integer]==0){
                    detectCycle(integer);
                }
                else if(visited[integer]==2) {
                    isCyclic = true;
                    return;
                }

            }
            visited[src] = 1;
        }
        static class FastReader {
            BufferedReader br;
            StringTokenizer st;
            public FastReader() {
                br = new BufferedReader(new
                        InputStreamReader(System.in));
            }
            String next() {
                while (st == null || !st.hasMoreElements()) {
                    try {
                        st = new StringTokenizer(br.readLine());
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
                return st.nextToken();
            }
            int nextInt() {
                return Integer.parseInt(next());
            }
            long nextLong() {
                return Long.parseLong(next());
            }
            double nextDouble() {
                return Double.parseDouble(next());
            }
            String nextLine() {
                String str = "";
                try {
                    str = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                return str;
            }
        }

        static class Pair implements Comparable< Pair> {
            private int ID;
            private int wins;

            public void setID(int ID) {
                this.ID = ID;
            }

            public void setWins(int wins) {
                this.wins = wins;
            }

            public Pair(int ID, int value) {
                this.ID = ID;
                this.wins = value;
            }
            public int second() {
                return wins;
            }
            @Override
            public int compareTo(Pair o) {
                //   out.println(o.wins +" " + wins);
                int winVal = Integer.compare(o.wins, wins);
                //  dbg(winVal);
                if(winVal==0){
                    return -Integer.compare(o.ID,ID);
                }
                return winVal;
            }
            @Override
            public String toString() {
                return "Pair{" + "x=" + ID + ", y=" + wins + '}';
            }
        }
        static <Array, Target> int count(Array[] array, Target target){
            int cn=0;
            for (Array value : array) {
                if (value.equals(target)) cn++;
            }
            return cn;
        }
        static int count (String string , char target){
            int cn=0;
            for (int i = 0; i < string.length(); i++) {
                if(string.charAt(i)==target)cn++;
            }
            return cn;
        }
        static  <Array> void revArray(Array [] arr) {
            int n = arr.length;
            for (int i = 0; i < n / 2; i++) {
                Array temp = arr[i];
                arr[i] = arr[n - i - 1];
                arr[n - i - 1] = temp;
            }

        }
        static <Array> void printArray(Array [] arr) {
            int n = arr.length;
            for (Array array : arr)out.print(array + " ");
            out.println();
        }
        static void yes() {out.println("YES");}
        static void no() {out.println("NO");}
        public static boolean isPal(String s)
        {
            StringBuilder stringBuilder = new StringBuilder(s);
            return s.equals(stringBuilder.reverse().toString());
        }
        public static int lowerBound(Integer[] array, int length, int value) {
            int low = -1;
            int hi = length;
            while (low + 1 < hi) {
                int mid = (low + hi) / 2;
                if (array[mid] <= value) {
                    low = mid;
                } else {
                    hi = mid;
                }
            }
            return low;
        }
        public static int upperBound(Integer[] array, int length, int value) {
            int low = -1;
            int hi = length;
            while (low + 1 < hi) {
                int mid = (low + hi) >> 1;
                if (array[mid] >= value) {
                    hi = mid;
                } else low = mid;
            }
            return hi;
        }
        public static int binarySearch(Integer[] arr, int length, int value) {
            int low = 0;
            int hi = length - 1;
            int ans = -1;
            while (low <= hi) {
                int mid = (low + hi) >> 1;
                if (arr[mid] > value) {
                    hi = mid - 1;
                } else if (arr[mid] < value) {
                    low = mid + 1;
                } else {
                    ans = mid;
                    break;
                }
            }
            return ans;
        }
        public static int gcd(int a, int b) {
            return b==0?a:gcd(b, a % b);
        }
        public static int lcm(int a, int b) {
            return a / gcd(a, b) * b;
        }
        public static int countDivs(int n) {
            int cn = 0;
            int sqr = (int) Math.sqrt(n);
            for (int i = 1; i <= sqr; ++i) {
                if (n % i == 0) {
                    ++cn;
                }
            }
            cn *= 2;
            if (sqr * sqr == n) cn--;
            return cn;
        }

        static void prime(int x) {
            //sieve algorithm. nlog(log(n)).
            prime = new boolean[(x + 1)];
            Arrays.fill(prime, true);
            prime[0] = prime[1] = false;
            for (int i = 2; i * i <= x; i++)
                if (prime[i])
                    for (int j = i * i; j <= x; j += i)
                        prime[j] = false;
        }
        static boolean isEven(long x) {
            return x % 2 == 0;
        }
        static boolean isPrime(long x) {
            boolean flag = true;
            int sqr = (int) Math.sqrt(x);
            if (x < 2) return false;
            for (int i = 2; i <= sqr; i++) {
                if (x % i == 0) {
                    flag = false;
                    break;
                }
            }
            return flag;
        }

        static long factorial(long x) {
            long total = 1;
            for (int i = 2; i <= x; i++)
                total = (total * i) % M;
            return total;
        }
        static long power1(long x, long y, long p)
        {
            long res = 1; // Initialize result

            x = x % p; // Update x if it is more than or
            // equal to p

            if (x == 0)
                return 0; // In case x is divisible by p;

            while (y > 0)
            {

                // If y is odd, multiply x with result
                if ((y & 1) != 0)
                    res = (res * x) % p;

                // y must be even now
                y = y >> 1; // y = y/2
                x = (x * x) % p;
            }
            return res;
        }
        static long power(long x, long n) {
            if (n == 0) {
                return 1;
            }
            long pow = power(x, n / 2L);
            if ((n & 1) == 1) {
                return (x%MM * (pow%MM) * (pow%MM))%MM;
            }
            return (pow%MM * pow%MM)%MM;
        }
        private static <T> String ts(T t) {
            if(t==null) {
                return "null";
            }
            try {
                return ts((Iterable) t);
            }catch(ClassCastException e) {
                if(t instanceof int[]) {
                    String s = Arrays.toString((int[]) t);
                    return "{"+s.substring(1, s.length()-1)+"}";
                }else if(t instanceof long[]) {
                    String s = Arrays.toString((long[]) t);
                    return "{"+s.substring(1, s.length()-1)+"}";
                }else if(t instanceof char[]) {
                    String s = Arrays.toString((char[]) t);
                    return "{"+s.substring(1, s.length()-1)+"}";
                }else if(t instanceof double[]) {
                    String s = Arrays.toString((double[]) t);
                    return "{"+s.substring(1, s.length()-1)+"}";
                }else if(t instanceof boolean[]) {
                    String s = Arrays.toString((boolean[]) t);
                    return "{"+s.substring(1, s.length()-1)+"}";
                }
                try {
                    return ts((Object[]) t);
                }catch(ClassCastException e1) {
                    return t.toString();
                }
            }
        }
        private static <T> String ts(T[] arr) {
            StringBuilder ret = new StringBuilder();
            ret.append("{");
            boolean first = true;
            for(T t: arr) {
                if(!first) {
                    ret.append(", ");
                }
                first = false;
                ret.append(ts(t));
            }
            ret.append("}");
            return ret.toString();
        }
        private static <T> String ts(Iterable<T> iter) {
            StringBuilder ret = new StringBuilder();
            ret.append("{");
            boolean first = true;
            for(T t: iter) {
                if(!first) {
                    ret.append(", ");
                }
                first = false;
                ret.append(ts(t));
            }
            ret.append("}");
            return ret.toString();
        }
        public static void dbg(Object... o) {
            if(LOCAL) {
                System.err.print("Line #"+Thread.currentThread().getStackTrace()[2].getLineNumber()+": [");
                for(int i = 0; i<o.length; i++) {
                    if(i!=0) {
                        System.err.print(", ");
                    }
                    System.err.print(ts(o[i]));
                }
                System.err.println("]");
            }
        }

    }
