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.IOException;
import java.io.InputStream;
import java.io.PrintWriter; // System.out is a PrintStream
import java.util.HashSet;
import java.util.InputMismatchException;


public class B {
    private static int MOD = (int)1e9 + 7, mod = 99_82_44_353;
    private static double PI = 3.14159265358979323846;

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        FasterScanner scn = new FasterScanner();
        PrintWriter out = new PrintWriter(System.out);
        for (int tc = scn.nextInt(); tc > 0; tc--) {
            int N = scn.nextInt(), K = scn.nextInt();
            HashSet<Integer>[] graph = new HashSet[N];
            int[][] que = new int[K][];
            for (int i = 0; i < N; i++) {
                graph[i] = new HashSet<>();
            }
            DSU st = new DSU(N);
            boolean flag = false;
            HashSet<String> al = new HashSet<>();
            for (int i = 0; i < K; i++) {
                que[i] = new int[] { scn.nextInt() - 1, scn.nextInt() - 1, scn.nextInt() - 1 };
            }
            for (int i = 0; i < K; i++) {
                flag = st.union(que[i][0], que[i][1]);
                if (flag) {
                    al.add((que[i][0] + 1) + " " + (que[i][1] + 1));
                }
            }
            for (int i = 0; i < K; i++) {
                flag = st.union(que[i][0], que[i][2]);
                if (flag) {
                    al.add((que[i][0] + 1) + " " + (que[i][2] + 1));
                }
            }
            boolean[] vis = new boolean[N];
            for (int i = 0; i < N; i++) {
                if (vis[i]) continue;
                if (i != 0) {
                    al.add("1 " + (i + 1));
                }
                dfs(i, graph, vis, al);
            }
            for (String s : al) {
                out.println(s);
            }
        }
        out.close();
    }

    private static void dfs(int src, HashSet<Integer>[] graph, boolean[] vis, HashSet<String> al) {
        vis[src] = true;
        for (int e : graph[src]) {
            if (vis[e]) continue;
            dfs(e, graph, vis, al);
        }
    }

    /* ------------------- Sorting ------------------- */
    private static void ruffleSort(int[] arr) {
        // int N = arr.length;
        // Random rand = new Random();
        // for (int i = 0; i < N; i++) {
        //     int oi = rand.nextInt(N), temp = arr[i];
        //     arr[i] = arr[oi];
        //     arr[oi] = temp;
        // }
        // Arrays.sort(arr);
    }
        
    /* ------------------- Sorting ------------------- */
    
    private static boolean isPalindrome(String str) {
        for (int i = 0, j = str.length() - 1; i < j; i++, j--) {
            if (str.charAt(i) != str.charAt(j)) {
                return false;
            }
        }
        return true;
    }
    
    private static boolean isPalindrome(char[] str) {
        for (int i = 0, j = str.length - 1; i < j; i++, j--) {
            if (str[i] != str[j]) {
                return false;
            }
        }
        return true;
    }
    
    /* ------------------- Pair class ------------------- */
    private static class Pair implements Comparable<Pair> {
		int x, y;
		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
		public int compareTo(Pair o) {
			return this.x == o.x ? this.y - o.y : this.x - o.x;
		}
	}

    /* ------------------- HCF and LCM ------------------- */
    private static int gcd(int num1, int num2) {
        int temp = 0;
        while (num2 != 0) {
            temp = num1;
            num1 = num2;
            num2 = temp % num2;
        }
        return num1;
    }
    
    private static int lcm(int num1, int num2) {
        return (int)((1L * num1 * num2) / gcd(num1, num2));
    }
    
    /* ------------------- primes and prime factorization ------------------- */
    private static boolean[] seive(int N) {
        // true means not prime, false means is a prime number :)
        boolean[] notPrimes = new boolean[N + 1];
        notPrimes[0] = notPrimes[1] = true;
        for (int i = 2; i * i <= N; i++) {
            if (notPrimes[i]) continue;
            for (int j = i * i; j <= N; j += i) {
                notPrimes[j] = true;
            }
        }
        return notPrimes;
    }

	/*
    private static TreeMap<Integer, Integer> primeFactors(long N) {
		TreeMap<Integer, Integer> primeFact = new TreeMap<>();
		for (int i = 2; i <= Math.sqrt(N); i++) {
            int count = 0;
            while (N % i == 0) {
                N /= i;
                count++;
            }
            if (count != 0) {
                primeFact.put(i, count);
            }
		}
		if (N != 1) {
            primeFact.put((int)N, 1);
        }
		return primeFact;
	}
    */

    /* ------------------- Binary Search ------------------- */
    private static long factorial(int N) {
        long ans = 1L;
        for (int i = 2; i <= N; i++) {
            ans *= i;
        }
        return ans;
    }

    private static long[] factorialDP(int N) {
        long[] factDP = new long[N + 1];
        factDP[0] = factDP[1] = 1;
        for (int i = 2; i <= N; i++) {
            factDP[i] = factDP[i - 1] * i;
        }
        return factDP;
    }

    private static long factorialMod(int N, int mod) {
        long ans = 1L;
        for (int i = 2; i <= N; i++) {
            ans = ((ans % mod) * (i % mod)) % mod;
        }
        return ans;
    }

    /* ------------------- Binary Search ------------------- */
    private static int floorSearch(int[] arr, int st, int ed, int tar) {
        int ans = -1;
        while (st <= ed) {
            int mid = ((ed - st) >> 1) + st;
            if (arr[mid] <= tar) {
                ans = mid;
                st = mid + 1;
            } else {
                ed = mid - 1;
            }
        }
        return ans;
    }
    
    private static int ceilingSearch(int[] arr, int st, int ed, int tar) {
        int ans = -1;
        while (st <= ed) {
            int mid = ((ed - st) >> 1) + st;
            if (arr[mid] < tar) {
                st = mid + 1;
            } else {
                ans = mid;
                ed = mid - 1;
            }
        }
        return ans;
    }
    
    /* ------------------- Power Function ------------------- */
    public static long pow(long x, long y) {
        long res = 1;
		while (y > 0) {
            if ((y & 1) != 0) {
                res = (res * x);
				y--;
			}
			x = (x * x);
			y >>= 1;
		}
		return res;
	}
    
	public static long powMod(long x, long y, int mod) {
        long res = 1;
		while (y > 0) {
            if ((y & 1) != 0) {
                res = (res * x) % mod;
				y--;
			}
			x = (x * x) % mod;
			y >>= 1;
		}
		return res % mod;
	}

    /* ------------------- Disjoint Set(Union and Find) ------------------- */
    private static class DSU {
		public int[] parent, rank;
		DSU(int N) {
			parent = new int[N];
			rank = new int[N];
			for (int i = 0; i < N; i++) {
				parent[i] = i;
                rank[i] = 1;
            }
		}
		public int find(int a) {
			if (parent[a] == a) {
				return a;
            }
            return parent[a] = find(parent[a]);
		}
		public boolean union(int a, int b) {
			int parA = find(a), parB = find(b);
			if (parA == parB) return false;
			if (rank[parA] > rank[parB]) {
                parent[parB] = parA;
            } else if (rank[parA] < rank[parB]) {
                parent[parA] = parB;
            } else {
                parent[parA] = parB;
                rank[parB]++;
            }
            return true;
		}
	}
    
    /* ------------------- Scanner class for input ------------------- */
    
    private static class FasterScanner {
		private InputStream stream;
		private byte[] buffer = new byte[1024];
		private int curChar, numChars;
		private SpaceCharFilter filter;

		public FasterScanner() {
            // default
			this.stream = System.in;
		}

		public FasterScanner(InputStream stream) {
			this.stream = stream;
		}

		private int readChar() {
			if (numChars == -1) {
				throw new InputMismatchException();
            }
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buffer);
				} catch (IOException e) {
					throw new InputMismatchException(e.getMessage());
				}
				if (numChars <= 0) {
					return -1;
                }
			}
			return buffer[curChar++];
		}

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

		private boolean isNewLine(int ch) {
			if (filter != null) {
				return filter.isNewLine(ch);
            }
			return ch == '\r' || ch == '\n' || ch == -1;
		}

        public char nextChar() {
            int ch = readChar();
            char res = '\0';
            while (isWhiteSpace(ch)) {
                ch = readChar();
            }
            do {
                res = (char)ch;
                ch = readChar();
            } while (!isWhiteSpace(ch));
            return res;
        }

		public String next() {
			int ch = readChar();
            StringBuilder res = new StringBuilder();
			while (isWhiteSpace(ch)) {
				ch = readChar();
            }
			do {
				res.appendCodePoint(ch);
				ch = readChar();
			} while (!isWhiteSpace(ch));
			return res.toString();
		}

		public String nextLine() {
			int ch = readChar();
            StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(ch);
				ch = readChar();
			} while (!isNewLine(ch));
			return res.toString();
		}

		public int nextInt() {
			int ch = -1, sgn = 1, res = 0;
            do {
                ch = readChar();
            } while (isWhiteSpace(ch));
			if (ch == '-') {
				sgn = -1;
				ch = readChar();
			}
			do {
				if (ch < '0' || ch > '9') {
					throw new InputMismatchException("not a number");
                }
				res = (res * 10) + (ch - '0');
				ch = readChar();
			} while (!isWhiteSpace(ch));
            
			return res * sgn;
		}

		public long nextLong() {
			int ch = -1, sgn = 1;
            long res = 0L;
            do {
                ch = readChar();
            } while (isWhiteSpace(ch));
			if (ch == '-') {
				sgn = -1;
				ch = readChar();
			}
			do {
				if (ch < '0' || ch > '9') {
					throw new InputMismatchException("not a number");
                }
				res = (10L * res) + (ch - '0');
				ch = readChar();
			} while (!isWhiteSpace(ch));

			return 1L * res * sgn;
		}

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        /* for custom delimiters */
		public interface SpaceCharFilter {
			public boolean isWhiteSpace(int ch);
			public boolean isNewLine(int ch);
		}
	}
}
