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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 105;
int n;
int cnt[kMaxN];
vector<pair<int, int>> edges[kMaxN];
vector<int> v[kMaxN];
vector<int> g[kMaxN];
bool was[kMaxN];
bool viz[kMaxN];
int grad[kMaxN];
vector<vector<vector<int>>> global_hashes;
void Reset(int n) {
  for (int i = 0; i <= n; i++) {
    v[i].clear();
    g[i].clear();
    edges[i].clear();
  }
  memset(cnt, 0, sizeof(cnt));
  memset(was, 0, sizeof(was));
  memset(viz, 0, sizeof(viz));
  memset(grad, 0, sizeof(grad));
  global_hashes.clear();
}
void dfs(int x) {
  viz[x] = 1;
  for (auto it : g[x]) {
    if (!viz[it]) {
      dfs(it);
      grad[x]++;
      grad[it]++;
    }
  }
}
bool Go() {
  vector<vector<vector<int>>> all_hashes;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      g[j].clear();
    }
    for (int j = 1; j <= n; j++) {
      if (i != j) {
        for (auto it : v[j]) {
          if (i != it) {
            g[j].push_back(it);
          }
        }
      }
    }
    memset(viz, 0, sizeof(viz));
    vector<vector<int>> curr_hash;
    for (int j = 1; j <= n; j++) {
      if (!viz[j]) {
        memset(grad, 0, sizeof(grad));
        dfs(j);
        vector<int> curr_grade;
        for (int k = 1; k <= n; k++) {
          if (grad[k]) {
            curr_grade.push_back(grad[k]);
          }
        }
        sort((curr_grade).begin(), (curr_grade).end());
        curr_hash.push_back(curr_grade);
      }
    }
    sort((curr_hash).begin(), (curr_hash).end());
    all_hashes.push_back(curr_hash);
  }
  sort((all_hashes).begin(), (all_hashes).end());
  return all_hashes == global_hashes;
}
void dfsPrint(int x) {
  viz[x] = 1;
  for (auto it : v[x]) {
    if (!viz[it]) {
      cout << it << " " << x << '\n';
      dfsPrint(it);
    }
  }
}
int main() {
  cin.sync_with_stdio(false);
  int t;
  cin >> t;
  for (; t; t--) {
    cin >> n >> n;
    Reset(n);
    int best = -1;
    for (int i = 1; i <= n; i++) {
      cin >> cnt[i];
      for (int j = 1; j <= cnt[i]; j++) {
        int x, y;
        cin >> x >> y;
        edges[i].push_back({x, y});
      }
      if (cnt[i] == n - 2) {
        best = i;
      }
    }
    if (best == -1) {
      cout << "NO\n";
      continue;
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        g[j].clear();
      }
      for (int j = 0; j < cnt[i]; j++) {
        int x = edges[i][j].first;
        int y = edges[i][j].second;
        g[x].push_back(y);
        g[y].push_back(x);
      }
      memset(viz, 0, sizeof(viz));
      vector<vector<int>> curr_hash;
      for (int j = 1; j <= n; j++) {
        if (!viz[j]) {
          memset(grad, 0, sizeof(grad));
          dfs(j);
          vector<int> curr_grade;
          for (int k = 1; k <= n; k++) {
            if (grad[k]) {
              curr_grade.push_back(grad[k]);
            }
          }
          sort((curr_grade).begin(), (curr_grade).end());
          curr_hash.push_back(curr_grade);
        }
      }
      sort((curr_hash).begin(), (curr_hash).end());
      global_hashes.push_back(curr_hash);
    }
    sort((global_hashes).begin(), (global_hashes).end());
    for (int i = 0; i < cnt[best]; i++) {
      int x = edges[best][i].first;
      int y = edges[best][i].second;
      v[x].push_back(y);
      v[y].push_back(x);
      was[x] = 1;
      was[y] = 1;
    }
    int missing = -1;
    for (int i = 1; i <= n; i++) {
      if (!was[i]) {
        missing = i;
      }
    }
    if (missing == -1) {
      cout << "NO\n";
      continue;
    }
    bool found = 0;
    for (int i = 1; i <= n; i++) {
      if (was[i]) {
        v[missing].push_back(i);
        v[i].push_back(missing);
        if (Go()) {
          cout << "YES\n";
          memset(viz, 0, sizeof(viz));
          dfsPrint(1);
          found = 1;
          break;
        }
        v[missing].pop_back();
        v[i].pop_back();
      }
    }
    if (!found) {
      cout << "NO\n";
    }
  }
  return 0;
}