#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 123;
const int BASE = 1e9 + 9;
int add(int a, int b) { return a + b - (a + b >= MOD) * MOD; }
int sub(int a, int b) { return a - b + (a - b < 0) * MOD; }
int mult(int a, int b) { return (1LL * a * b) % MOD; }
int collapse(vector<int> has) {
  sort(has.begin(), has.end());
  int res = 0;
  for (int i : has) res = add(mult(res, BASE), i);
  return res;
}
int n;
vector<vector<int> > adj;
int s[113];
bool vis[113];
void setup(int x, int p = 0) {
  vis[x] = 1;
  s[x] = 1;
  for (int i : adj[x])
    if (i != p) {
      setup(i, x);
      s[x] += s[i];
    }
}
void look(int x, int p, int tot, vector<int>& centroids) {
  bool ok = 1;
  for (int i : adj[x])
    if (i != p) {
      if (s[i] > tot / 2) ok = 0;
      look(i, x, tot, centroids);
    }
  if (tot - s[x] > tot / 2) ok = 0;
  if (ok) centroids.push_back(x);
}
int process(int x, int p = 0) {
  vector<int> res;
  res.push_back(1);
  for (int i : adj[x])
    if (i != p) {
      res.push_back(mult(2, process(i, x)));
    }
  return collapse(res);
}
int idTree(int x) {
  setup(x);
  vector<int> centroids;
  look(x, 0, s[x], centroids);
  int res = 0;
  for (int c : centroids) {
    res = max(res, process(c));
  }
  return res;
}
int idForest() {
  memset(vis, 0, sizeof vis);
  vector<int> res;
  for (int i = 1; i <= n; i++)
    if (!vis[i]) {
      res.push_back(idTree(i));
    }
  return collapse(res);
}
vector<vector<int> > drawing[113];
bool test(int i, int a, int b, int id) {
  vector<int> res;
  for (int r = 1; r <= n; r++) {
    adj.clear();
    adj.resize(n + 1);
    for (int j = 1; j <= n; j++) {
      for (int k : drawing[i][j]) {
        if (j != r && k != r) {
          adj[j].push_back(k);
        }
      }
    }
    if (a != r && b != r) {
      adj[a].push_back(b);
      adj[b].push_back(a);
    }
    res.push_back(idForest());
  }
  return collapse(res) == id;
}
void solve() {
  scanf("%d%*d", &n);
  for (int i = 0; i < n; i++) {
    drawing[i].clear();
    drawing[i].resize(n + 1);
  }
  for (int i = 0; i < n; i++) {
    int m;
    scanf("%d", &m);
    for (int j = 0; j < m; j++) {
      int a, b;
      scanf("%d%d", &a, &b);
      drawing[i][a].push_back(b);
      drawing[i][b].push_back(a);
    }
  }
  vector<int> res;
  for (int i = 0; i < n; i++) {
    adj = drawing[i];
    res.push_back(idForest());
  }
  int id = collapse(res);
  for (int i = 0; i < n; i++) {
    adj = drawing[i];
    int on = 1;
    while (on < n && !adj[on].size()) on += 1;
    memset(vis, 0, sizeof vis);
    setup(on);
    int num = accumulate(vis, vis + n + 1, 0);
    if (num == n - 1) {
      num = 1;
      while (vis[num]) num += 1;
      for (int j = 1; j <= n; j++) {
        if (j != num && test(i, num, j, id)) {
          printf("YES\n");
          for (int a = 1; a <= n; a++) {
            for (int b : drawing[i][a]) {
              if (b > a) printf("%d %d\n", a, b);
            }
          }
          printf("%d %d\n", num, j);
          return;
        }
      }
      printf("NO\n");
      return;
    }
  }
  printf("NO\n");
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) solve();
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

Heidi got tired of deciphering the prophecy hidden in the Tree of Life and decided to go back to her headquarters, rest a little and try there. Of course, she cannot uproot the Tree and take it with her, so she made a drawing of the Tree on a piece of paper. On second thought, she made more identical drawings so as to have n in total (where n is the number of vertices of the Tree of Life) – who knows what might happen?

Indeed, on her way back Heidi was ambushed by a group of zombies. While she managed to fend them off, they have damaged her drawings in a peculiar way: from the i-th copy, the vertex numbered i was removed, along with all adjacent edges. In each picture, the zombies have also erased all the vertex numbers and relabeled the remaining n - 1 vertices arbitrarily using numbers 1 to n (fortunately, each vertex still has a distinct number). What's more, the drawings have been arbitrarily shuffled/reordered.

Now Heidi wants to recover the Tree of Life from her descriptions of all the drawings (as lists of edges).

Input

The first line of the input contains Z ≤ 20 – the number of test cases. Z descriptions of single test cases follow.

In each test case, the first line of input contains numbers n (2 ≤ n ≤ 100) and k (where k is the number of drawings; we have k = n). In the following lines, the descriptions of the k drawings are given. The description of the i-th drawing is a line containing mi – the number of edges in this drawing, followed by mi lines describing edges, each of which contains two space-separated integers –- the numbers of the two vertices connected by the edge.

Output

If Heidi's drawings cannot possibly come from a single tree, you should output the word NO. Otherwise, output one line containing the word YES and n - 1 lines describing any tree that Heidi's drawings could have come from. For every edge you should output the numbers of the vertices that it connects, separated with a single space. If there are many solutions, print any of them.

Example

Input

1
5 5
2
4 1
2 1
1
3 1
3
4 1
4 3
2 1
3
3 1
3 2
4 1
3
2 1
3 2
4 2


Output

YES
2 5
4 2
3 2
5 1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 123;
const int BASE = 1e9 + 9;
int add(int a, int b) { return a + b - (a + b >= MOD) * MOD; }
int sub(int a, int b) { return a - b + (a - b < 0) * MOD; }
int mult(int a, int b) { return (1LL * a * b) % MOD; }
int collapse(vector<int> has) {
  sort(has.begin(), has.end());
  int res = 0;
  for (int i : has) res = add(mult(res, BASE), i);
  return res;
}
int n;
vector<vector<int> > adj;
int s[113];
bool vis[113];
void setup(int x, int p = 0) {
  vis[x] = 1;
  s[x] = 1;
  for (int i : adj[x])
    if (i != p) {
      setup(i, x);
      s[x] += s[i];
    }
}
void look(int x, int p, int tot, vector<int>& centroids) {
  bool ok = 1;
  for (int i : adj[x])
    if (i != p) {
      if (s[i] > tot / 2) ok = 0;
      look(i, x, tot, centroids);
    }
  if (tot - s[x] > tot / 2) ok = 0;
  if (ok) centroids.push_back(x);
}
int process(int x, int p = 0) {
  vector<int> res;
  res.push_back(1);
  for (int i : adj[x])
    if (i != p) {
      res.push_back(mult(2, process(i, x)));
    }
  return collapse(res);
}
int idTree(int x) {
  setup(x);
  vector<int> centroids;
  look(x, 0, s[x], centroids);
  int res = 0;
  for (int c : centroids) {
    res = max(res, process(c));
  }
  return res;
}
int idForest() {
  memset(vis, 0, sizeof vis);
  vector<int> res;
  for (int i = 1; i <= n; i++)
    if (!vis[i]) {
      res.push_back(idTree(i));
    }
  return collapse(res);
}
vector<vector<int> > drawing[113];
bool test(int i, int a, int b, int id) {
  vector<int> res;
  for (int r = 1; r <= n; r++) {
    adj.clear();
    adj.resize(n + 1);
    for (int j = 1; j <= n; j++) {
      for (int k : drawing[i][j]) {
        if (j != r && k != r) {
          adj[j].push_back(k);
        }
      }
    }
    if (a != r && b != r) {
      adj[a].push_back(b);
      adj[b].push_back(a);
    }
    res.push_back(idForest());
  }
  return collapse(res) == id;
}
void solve() {
  scanf("%d%*d", &n);
  for (int i = 0; i < n; i++) {
    drawing[i].clear();
    drawing[i].resize(n + 1);
  }
  for (int i = 0; i < n; i++) {
    int m;
    scanf("%d", &m);
    for (int j = 0; j < m; j++) {
      int a, b;
      scanf("%d%d", &a, &b);
      drawing[i][a].push_back(b);
      drawing[i][b].push_back(a);
    }
  }
  vector<int> res;
  for (int i = 0; i < n; i++) {
    adj = drawing[i];
    res.push_back(idForest());
  }
  int id = collapse(res);
  for (int i = 0; i < n; i++) {
    adj = drawing[i];
    int on = 1;
    while (on < n && !adj[on].size()) on += 1;
    memset(vis, 0, sizeof vis);
    setup(on);
    int num = accumulate(vis, vis + n + 1, 0);
    if (num == n - 1) {
      num = 1;
      while (vis[num]) num += 1;
      for (int j = 1; j <= n; j++) {
        if (j != num && test(i, num, j, id)) {
          printf("YES\n");
          for (int a = 1; a <= n; a++) {
            for (int b : drawing[i][a]) {
              if (b > a) printf("%d %d\n", a, b);
            }
          }
          printf("%d %d\n", num, j);
          return;
        }
      }
      printf("NO\n");
      return;
    }
  }
  printf("NO\n");
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) solve();
  return 0;
}

```