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.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.lang.*;
import java.io.*;


public class cf2 {
    static PrintWriter out;
    static int MOD = 1000000007;
    static FastReader scan;

    /*-------- I/O using short named function ---------*/
    public static String ns() {
        return scan.next();
    }

    public static int ni() {
        return scan.nextInt();
    }

    public static long nl() {
        return scan.nextLong();
    }

    public static double nd() {
        return scan.nextDouble();
    }

    public static String nln() {
        return scan.nextLine();
    }

    public static void p(Object o) {
        out.print(o);
    }

    public static void ps(Object o) {
        out.print(o + " ");
    }

    public static void pn(Object o) {
        out.println(o);
    }

    /*-------- for output of an array ---------------------*/
    static void iPA(int arr[]) {
        StringBuilder output = new StringBuilder();
        for (int i = 0; i < arr.length; i++) output.append(arr[i] + " ");
        out.println(output);
    }

    static void lPA(long arr[]) {
        StringBuilder output = new StringBuilder();
        for (int i = 0; i < arr.length; i++) output.append(arr[i] + " ");
        out.println(output);
    }

    static void sPA(String arr[]) {
        StringBuilder output = new StringBuilder();
        for (int i = 0; i < arr.length; i++) output.append(arr[i] + " ");
        out.println(output);
    }

    static void dPA(double arr[]) {
        StringBuilder output = new StringBuilder();
        for (int i = 0; i < arr.length; i++) output.append(arr[i] + " ");
        out.println(output);
    }

    /*-------------- for input in an array ---------------------*/
    static void iIA(int arr[]) {
        for (int i = 0; i < arr.length; i++) arr[i] = ni();
    }

    static void lIA(long arr[]) {
        for (int i = 0; i < arr.length; i++) arr[i] = nl();
    }

    static void sIA(String arr[]) {
        for (int i = 0; i < arr.length; i++) arr[i] = ns();
    }

    static void dIA(double arr[]) {
        for (int i = 0; i < arr.length; i++) arr[i] = nd();
    }

    /*------------ for taking input faster ----------------*/
    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;
        }
    }

    public static ArrayList<Integer> sieveOfEratosthenes(int n) {
        // Create a boolean array
        // "prime[0..n]" and
        // initialize all entries
        // it as true. A value in
        // prime[i] will finally be
        // false if i is Not a
        // prime, else true.
        boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = true;

        for (int p = 2; p * p <= n; p++) {
            // If prime[p] is not changed, then it is a
            // prime
            if (prime[p] == true) {
                // Update all multiples of p
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
        ArrayList<Integer> arr = new ArrayList<>();
        // store all prime numbers
        for (int i = 2; i <= n; i++) {
            if (prime[i] == true)
                arr.add(i);
        }
        return arr;
    }

    // Method to check if x is power of 2
    static boolean isPowerOfTwo(int x) {
        return x != 0 && ((x & (x - 1)) == 0);
    }

    //Method to return lcm of two numbers
    static int gcd(int a, int b) {
        return a == 0 ? b : gcd(b % a, a);
    }

    //Method to count digit of a number
    static int countDigit(long n) {
        String sex = Long.toString(n);
        return sex.length();
    }

    static void reverse(int a[]) {
        int i, k, t;
        int n = a.length;
        for (i = 0; i < n / 2; i++) {
            t = a[i];
            a[i] = a[n - i - 1];
            a[n - i - 1] = t;
        }
    }
    static long nCr(long n, long r)
    {
        long p = 1, k = 1;

        // C(n, r) == C(n, n-r),
        // choosing the smaller value
        if (n - r < r) {
            r = n - r;
        }

        if (r != 0) {
            while (r > 0) {
                p *= n;
                k *= r;

                // gcd of p, k
                long m = gcdlong(p, k);

                // dividing by gcd, to simplify
                // product division by their gcd
                // saves from the overflow
                p /= m;
                k /= m;

                n--;
                r--;
            }

            // k should be simplified to 1
            // as C(n, r) is a natural number
            // (denominator should be 1 ) .
        }
        else {
            p = 1;
        }

        // if our approach is correct p = ans and k =1
        return p;
    }
    static long gcdlong(long n1, long n2)
    {
        long gcd = 1;

        for (int i = 1; i <= n1 && i <= n2; ++i) {
            // Checks if i is factor of both integers
            if (n1 % i == 0 && n2 % i == 0) {
                gcd = i;
            }
        }
        return gcd;
    }

    // Returns factorial of n
    static long fact(long n)
    {
        long res = 1;
        for (long i = 2; i <= n; i++)
            res = res * i;
        return res;
    }
    // Get all prime numbers till N using seive of Eratosthenes
    public static List<Integer> getPrimesTill(int n){
        boolean[] arr = new boolean[n+1];
        List<Integer> primes = new LinkedList<>();
        for(int i=2; i<=n; i++){
            if(!arr[i]){
                primes.add(i);
                for(long j=(i*i); j<=n; j+=i){
                    arr[(int)j] = true;
                }
            }
        }
        return primes;
    }

    static final Random random = new Random();

    //Method for sorting
    static void ruffleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int j = random.nextInt(n);
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
        Arrays.sort(arr);
    }

    static void sortadv(long[] a) {
        ArrayList<Long> l = new ArrayList<>();
        for (long value : a) {
            l.add(value);
        }
        Collections.sort(l);
        for (int i = 0; i < l.size(); i++)
            a[i] = l.get(i);
    }

    //Method for checking if a number is prime or not
    static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        return true;
    }

    public static void main(String[] args) throws java.lang.Exception {
        OutputStream outputStream = System.out;
        out = new PrintWriter(outputStream);
        scan = new FastReader();
        //for fast output sometimes
        StringBuilder sb1 = new StringBuilder();

        // prefix sum, *dp , odd-even segregate , *brute force(n=100)(jo bola wo kar) , 2 pointer , pattern , see contraints
        // but first observe!   maybe just watch i-o like ans-x-1,y for input x,y;
        // divide wale ques me always check whether divisor 1?  || probability mei mostly (1-p)...
        // Deque<String> deque = new LinkedList<String>();
        // in mod ques take everything as long.

        int t =ni();
        while (t-- != 0) {
            int n=ni();
            int m=ni();
            int[] a=new int[m];
            int[] b=new int[m];
            ArrayList<Integer> adj[]=new ArrayList[n+1];
            for(int i=1;i<n+1;i++){
                adj[i]=new ArrayList<>();
            }
            for(int i=0;i<m;i++){
                a[i]=ni();int c=ni();b[i]=ni();
                adj[a[i]].add(b[i]);
            }
            HashSet<Integer> hs=new HashSet<>();
            for(int i=1;i<n+1;i++){
                for(int it:adj[i])
                {
                    if(!hs.contains(i)&&!hs.contains(it)) {
                        pn(i + " " + it);
                        if(a[0]!=i&&a[0]!=i)
                        pn(a[0]+" "+i);
                        hs.add(i);
                        hs.add(it);
                    }
                    else if(!hs.contains(i)||!hs.contains(it)) {
                        pn(i + " " + it);
                        hs.add(i);
                        hs.add(it);
                    }
                }
            }
            for(int i=1;i<n+1;i++){
                if(!hs.contains(i))
                    pn(a[0]+" "+i);
            }
        }
        out.flush();
        out.close();
    }

    static long binpow(long a,long b) {
        a %= MOD;
        long res = 1;
        while (b > 0) {
            if ((b & 1)==1)
                res = (res%MOD * a % MOD)%MOD;
            a = (a%MOD * a % MOD)%MOD;
            b >>= 1;
        }
        return res;
    }
    public static long findpow(int n,int i){
        long ans=1;
        for(int in=1;in<=i;in++)
            ans=(ans%MOD*n%MOD)%MOD;
        return ans;
    }
    public static String rev(String s,int m){
        char ch[]=new char[m];
        int j=m-1;
        for(int i=0;i<m;i++){
            ch[j--]=s.charAt(i);
        }
        return new String(ch);
    }
    public static boolean palin(String s,int i,int j){
        while(i<=j){
            if(s.charAt(i++)!=s.charAt(j--))
                return false;
        }
        return true;
    }
    public static int modInverse(int a, int m)
    {
        int m0 = m;
        int y = 0, x = 1;

        if (m == 1)
            return 0;

        while (a > 1) {
            // q is quotient
            int q = a / m;

            int t = m;

            // m is remainder now, process
            // same as Euclid's algo
            m = a % m;
            a = t;
            t = y;

            // Update x and y
            y = x - q * y;
            x = t;
        }

        // Make x positive
        if (x < 0)
            x += m0;

        return x;
    }
    public static int countodd(int[] a){
        int count=0;
        for(int i:a){
            if(i%2==1)
                count++;
        }
        return count;
    }
    static int minOps(String s, int si, int ei, char ch) {

        if (si == ei) {
            return ch == s.charAt(si) ? 0 : 1;
        }

        int mid =( si+ei) >>1;

        int leftC = minOps(s, si, mid, (char) (ch + 1));
        int rightC = minOps(s, mid + 1, ei, (char) (ch + 1));

        for (int i = si; i <= mid; i++) {
            if (s.charAt(i) != ch)
                rightC++;
        }

        for (int i = mid + 1; i <= ei; i++) {
            if (s.charAt(i) != ch)
                leftC++;
        }

        return Math.min(leftC, rightC);

    }
    public static int sumofdigit(long n){
        int sum=0;
        while(n!=0){
            sum+=n%10;
            n/=10;
        }
        return sum;
    }
    public static int computeXOR(int n)
    {
        // If n is a multiple of 4
        if (n % 4 == 0)
            return n;

        // If n%4 gives remainder 1
        if (n % 4 == 1)
            return 1;

        // If n%4 gives remainder 2
        if (n % 4 == 2)
            return n + 1;

        // If n%4 gives remainder 3
        return 0;
    }
    public static class Pair {
        int a, b;
        public Pair(int x,int y){
            a=x;b=y;
        }

    }
    private static boolean checkCycle(int node,  ArrayList<ArrayList<Integer>> adj, int vis[], int dfsVis[]) {
        vis[node] = 1;
        dfsVis[node] = 1;

        for(Integer it: adj.get(node)) {
            if(vis[it] == 0) {
                if(checkCycle(it, adj, vis, dfsVis) == true) {
                    return true;
                }
            } else if(dfsVis[it] == 1) {
                return true;
            }
        }
        dfsVis[node] = 0;
        return false;
    }
    public static boolean isCyclic(int N, ArrayList<ArrayList<Integer>> adj) {
        int vis[] = new int[N];
        int dfsVis[] = new int[N];

        for(int i = 0;i<N;i++) {
            if(vis[i] == 0) {
                if(checkCycle(i, adj, vis, dfsVis) == true) return true;
            }
        }
        return false;
    }
}



