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;
int n, T;
multiset<unsigned long long> se;
multiset<unsigned long long>::iterator it;
unsigned long long val[110];
struct tree {
  int m, top, f1, f2, sum, id;
  int vis[110], size[110], used[110], f[110];
  vector<int> v[110];
  vector<unsigned long long> v1[110];
  unsigned long long st[110];
  void dfs1(int x, int y) {
    size[x] = 1;
    used[x] = 1;
    for (int i = 0, t; i < v[x].size(); i++)
      if ((t = v[x][i]) != y && !vis[t]) dfs1(t, x), size[x] += size[t];
  }
  void dfs2(int x, int y) {
    f[x] = sum - size[x];
    for (int i = 0, t; i < v[x].size(); i++)
      if ((t = v[x][i]) != y && !vis[t]) dfs2(t, x), f[x] = max(f[x], size[t]);
    if (f[x] < f[f1])
      f1 = x;
    else if (f[x] < f[f2])
      f2 = x;
  }
  unsigned long long dfs3(int x, int y) {
    v1[x].clear();
    for (int i = 0, t; i < v[x].size(); i++)
      if ((t = v[x][i]) != y && !vis[t]) v1[x].push_back(dfs3(t, x));
    sort(v1[x].begin(), v1[x].end());
    unsigned long long ret = 1;
    for (int i = 0; i < v1[x].size(); i++) ret = ret * 11333333 + v1[x][i];
    return ret;
  }
  unsigned long long cal(int x) {
    f1 = f2 = 0;
    f[0] = 1 << 30;
    dfs1(x, 0);
    sum = size[x];
    dfs2(x, 0);
    if (f[f1] != f[f2]) return dfs3(f1, 0);
    unsigned long long t1 = dfs3(f1, f2);
    unsigned long long t2 = dfs3(f2, f1);
    if (t1 > t2) swap(t1, t2);
    return t1 * 11333333 + t2;
  }
  void init(int x) {
    scanf("%d", &m);
    id = x;
    for (int i = 1; i <= n; i++) v[i].clear();
    for (int i = 1, x, y; i <= m; i++) {
      scanf("%d%d", &x, &y);
      v[x].push_back(y);
      v[y].push_back(x);
    }
    memset(used, 0, sizeof(used));
    top = 0;
    for (int i = 1; i <= n; i++)
      if (!used[i]) st[++top] = cal(i);
    sort(st + 1, st + 1 + top);
    val[id] = 0;
    for (int i = 2; i <= top; i++) val[id] = val[id] * 11333333 + st[i];
  }
  int check() {
    se.clear();
    for (int i = 1; i <= n; i++) {
      vis[i] = 1;
      top = 0;
      for (int j = 0; j < v[i].size(); j++) st[++top] = cal(v[i][j]);
      vis[i] = 0;
      unsigned long long tmp = 0;
      sort(st + 1, st + 1 + top);
      for (int j = 1; j <= top; j++) tmp = tmp * 11333333 + st[j];
      se.insert(tmp);
    }
    for (int i = 1; i <= n; i++)
      if (i != id) {
        if ((it = se.find(val[i])) == se.end()) return 0;
        se.erase(it);
      }
    return 1;
  }
  void print() {
    puts("YES");
    for (int i = 1; i <= n; i++) {
      for (int j = 0, t; j < v[i].size(); j++)
        if ((t = v[i][j]) < i) printf("%d %d\n", t, i);
    }
  }
} tr[110];
void solve() {
  scanf("%d%*d", &n);
  for (int i = 1; i <= n; i++) tr[i].init(i);
  for (int i = 1; i <= n; i++)
    if (tr[i].top == 2) {
      for (int j = 1; j <= n; j++)
        if (tr[i].v[j].empty()) {
          for (int k = 1; k <= n; k++)
            if (k != j) {
              tr[i].v[k].push_back(j);
              tr[i].v[j].push_back(k);
              if (tr[i].check()) {
                tr[i].print();
                return;
              }
              tr[i].v[k].pop_back();
              tr[i].v[j].pop_back();
            }
        }
      break;
    }
  puts("NO");
}
int main() {
  scanf("%d", &T);
  while (T--) {
    solve();
  }
  return 0;
}