description: 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>
solution: import java.util.*;
  import java.io.*;
  
  public class B {
  
      class Restriction {
          int a, b, c;
  
          public Restriction(int _a, int _b, int _c) {
              a = _a;
              b = _b;
              c = _c;
          }
      }
  
      public void prayGod() throws IOException {
          int t = nextInt();
          while (t-- > 0) {
              int n = nextInt();
              int m = nextInt();
  
              boolean[] canBeRoot = new boolean[n];
              Arrays.fill(canBeRoot, true);
  
              Restriction[] restrictions = new Restriction[m];
              for (int i = 0; i < m; i++) {
                  restrictions[i] = new Restriction(nextInt() - 1, nextInt() - 1, nextInt() - 1);
                  canBeRoot[restrictions[i].b] = false;
              }
  
              int root = -1;
              for (int i = 0; i < n; i++) {
                  if (canBeRoot[i]) {
                      root = i;
                      break;
                  }
              }
  
              for (int i = 0; i < n; i++) {
                  if (i == root)
                      continue;
                  out.printf("%d %d\n", root + 1, i + 1);
              }
  
          }
      }
  
      public void printVerdict(boolean verdict) {
          if (verdict)
              out.println(VERDICT_YES);
          else
              out.println(VERDICT_NO);
      }
  
      static final String VERDICT_YES = "YES";
      static final String VERDICT_NO = "NO";
      static final boolean RUN_TIMING = true;
      static final boolean AUTOFLUSH = false;
      static final boolean FILE_INPUT = false;
      static final boolean FILE_OUTPUT = false;
  
      static int iinf = 0x3f3f3f3f;
      static long inf = (long) 1e18 + 10;
      static long mod = (long) 1e9 + 7;
  
      static char[] inputBuffer = new char[1 << 20];
      static PushbackReader in = new PushbackReader(new BufferedReader(new InputStreamReader(System.in)), 1 << 20);
      static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), AUTOFLUSH);
  
      // int data-type
      public int nextInt() throws IOException {
          return Integer.parseInt(next());
      }
  
      public int[] nextIntArray(int n) throws IOException {
          int[] arr = new int[n];
          for (int i = 0; i < n; i++)
              arr[i] = nextInt();
          return arr;
      }
  
      public void sort(int[] a) {
          shuffle(a);
          Arrays.sort(a);
      }
  
      public static void printArray(int[] arr) {
          for (int i = 0; i < arr.length; i++)
              out.print(arr[i] + " ");
          out.println();
      }
  
      // long data-type
      public long nextLong() throws IOException {
          return Long.parseLong(next());
      }
  
      public long[] nextLongArray(int n) throws IOException {
          long[] arr = new long[n];
          for (int i = 0; i < n; i++)
              arr[i] = nextLong();
          return arr;
      }
  
      public static void printArray(long[] arr) {
          for (int i = 0; i < arr.length; i++)
              out.print(arr[i] + " ");
          out.println();
      }
  
      public void sort(long[] a) {
          shuffle(a);
          Arrays.sort(a);
      }
  
      // double data-type
      public double nextDouble() throws IOException {
          return Double.parseDouble(next());
      }
  
      public double[] nextDoubleArray(int n) throws IOException {
          double[] arr = new double[n];
          for (int i = 0; i < n; i++)
              arr[i] = nextDouble();
          return arr;
      }
  
      public static void printArray(double[] arr) {
          for (int i = 0; i < arr.length; i++)
              out.print(arr[i] + " ");
          out.println();
      }
  
      // Generic type
      public <T> void sort(T[] a) {
          shuffle(a);
          Arrays.sort(a);
      }
  
      public static <T> void printArray(T[] arr) {
          for (int i = 0; i < arr.length; i++)
              out.print(arr[i] + " ");
          out.println();
      }
  
      public String next() throws IOException {
          int len = 0;
          int c;
          do {
              c = in.read();
          } while (Character.isWhitespace(c) && c != -1);
          if (c == -1) {
              throw new NoSuchElementException("Reached EOF");
          }
          do {
              inputBuffer[len] = (char) c;
              len++;
              c = in.read();
          } while (!Character.isWhitespace(c) && c != -1);
          while (c != '\n' && Character.isWhitespace(c) && c != -1) {
              c = in.read();
          }
          if (c != -1 && c != '\n') {
              in.unread(c);
          }
          return new String(inputBuffer, 0, len);
      }
  
      public String nextLine() throws IOException {
          int len = 0;
          int c;
          while ((c = in.read()) != '\n' && c != -1) {
              if (c == '\r') {
                  continue;
              }
              inputBuffer[len] = (char) c;
              len++;
          }
          return new String(inputBuffer, 0, len);
      }
  
      public boolean hasNext() throws IOException {
          String line = nextLine();
          if (line.isEmpty()) {
              return false;
          }
          in.unread('\n');
          in.unread(line.toCharArray());
          return true;
      }
  
      public void shuffle(int[] arr) {
          int n = arr.length;
          for (int i = 0; i < n; i++) {
              int j = (int) (Math.random() * (n - i));
              int temp = arr[i];
              arr[i] = arr[j];
              arr[j] = temp;
          }
      }
  
      public void shuffle(long[] arr) {
          int n = arr.length;
          for (int i = 0; i < n; i++) {
              int j = (int) (Math.random() * (n - i));
              long temp = arr[i];
              arr[i] = arr[j];
              arr[j] = temp;
          }
      }
  
      public void shuffle(Object[] arr) {
          int n = arr.length;
          for (int i = 0; i < n; i++) {
              int j = (int) (Math.random() * (n - i));
              Object temp = arr[i];
              arr[i] = arr[j];
              arr[j] = temp;
          }
      }
  
      public static void main(String[] args) throws IOException {
          if (FILE_INPUT)
              in = new PushbackReader(new BufferedReader(new FileReader(new File("output.txt"))), 1 << 20);
          if (FILE_OUTPUT)
              out = new PrintWriter(new FileWriter(new File("output.txt")));
  
          long time = 0;
          time -= System.nanoTime();
          new B().prayGod();
          time += System.nanoTime();
  
          if (RUN_TIMING)
              System.err.printf("%.3f ms%n", time / 1000000.0);
  
          out.flush();
          in.close();
      }
  }