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 N = 110, oo = 1000000000;
int ii, i, j, k, l, n, m, t, ch, Fg, Test, nm, tt;
vector<int> A, B;
map<vector<int>, int> Map;
void R(int &x) {
  x = 0;
  ch = getchar();
  while (ch < '0' || '9' < ch) ch = getchar();
  while ('0' <= ch && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
struct edge {
  int s, n;
};
struct forest {
  int i, j, k, m, En, x, y, rt1, rt2, mi1, mi2, size;
  int h[N], f[N], z[N], sz[N];
  edge E[N << 1];
  vector<int> A;
  void clear() {
    En = 0;
    memset(h, 0, sizeof h);
  }
  int getf(int x) {
    if (f[x] == x) return x;
    return f[x] = getf(f[x]);
  }
  void E_add(int x, int y) {
    E[++En].s = y;
    E[En].n = h[x];
    h[x] = En;
    E[++En].s = x;
    E[En].n = h[y];
    h[y] = En;
  }
  void read() {
    clear();
    for (i = 1; i <= n; i++) f[i] = i;
    R(m);
    for (i = 1; i <= m; i++) {
      R(x);
      R(y);
      if (getf(x) != getf(y))
        f[f[x]] = f[y];
      else
        Fg = 1;
      E_add(x, y);
    }
    k = 0;
    for (i = 1; i <= n; i++)
      if (h[i]) k++;
    if (k >= n) Fg = 1;
  }
  void write() {
    for (i = 1; i <= n; i++)
      for (k = h[i]; k; k = E[k].n)
        if (i < E[k].s) printf("%d %d\n", i, E[k].s);
  }
  void get_size(int x, int F) {
    sz[x] = 1;
    for (int k = h[x]; k; k = E[k].n)
      if (E[k].s != F) {
        get_size(E[k].s, x);
        sz[x] += sz[E[k].s];
      }
  }
  void get_root(int x, int F) {
    int ma = size - sz[x];
    for (int k = h[x]; k; k = E[k].n)
      if (E[k].s != F) {
        get_root(E[k].s, x);
        if (sz[E[k].s] > ma) ma = sz[E[k].s];
      }
    if (ma <= mi1) {
      mi2 = mi1;
      rt2 = rt1;
      mi1 = ma;
      rt1 = x;
    } else {
      if (ma < mi2) {
        mi2 = ma;
        rt2 = x;
      }
    }
  }
  int get_hash(int x) {
    z[x] = 1;
    vector<int> A;
    for (int k = h[x]; k; k = E[k].n)
      if (!z[E[k].s]) A.push_back(get_hash(E[k].s));
    sort(A.begin(), A.end());
    if (!Map[A]) Map[A] = ++nm;
    return Map[A];
  }
  int Js() {
    A.clear();
    memset(z, 0, sizeof z);
    for (i = 1; i <= n; i++)
      if (h[i] && !z[i]) {
        mi1 = mi2 = oo;
        get_size(i, 0);
        size = sz[i];
        get_root(i, 0);
        if (mi1 == mi2) {
          vector<int> tmp;
          tmp.push_back(-1);
          z[rt2] = 1;
          tmp.push_back(get_hash(rt1));
          z[rt2] = 0;
          tmp.push_back(get_hash(rt2));
          sort(tmp.begin(), tmp.end());
          if (!Map[tmp]) Map[tmp] = ++nm;
          A.push_back(Map[tmp]);
        } else
          A.push_back(get_hash(rt1));
      }
    sort(A.begin(), A.end());
    if (!Map[A]) Map[A] = ++nm;
    return Map[A];
  }
} F[N], G, tree;
int main() {
  R(Test);
  for (ii = 1; ii <= Test; ii++) {
    Fg = t = nm = 0;
    Map.clear();
    A.clear();
    R(n);
    R(m);
    for (i = 1; i <= n; i++) {
      F[i].read();
      if (!t && F[i].m == n - 2) t = i;
    }
    if (Fg || !t) {
      puts("NO");
      continue;
    }
    for (i = 1; i <= n; i++) A.push_back(F[i].Js());
    sort(A.begin(), A.end());
    for (tt = 1; tt <= n; tt++)
      if (!F[t].h[tt]) break;
    for (i = 1; i <= n; i++)
      if (i != tt) {
        B.clear();
        tree = F[t];
        tree.E_add(i, tt);
        for (j = 1; j <= n; j++) {
          G.clear();
          for (l = 1; l <= n; l++)
            if (l != j)
              for (k = tree.h[l]; k; k = tree.E[k].n)
                if (tree.E[k].s != j && l < tree.E[k].s)
                  G.E_add(l, tree.E[k].s);
          B.push_back(G.Js());
        }
        sort(B.begin(), B.end());
        if (A == B) {
          puts("YES");
          tree.write();
          break;
        }
      }
    if (i > n) puts("NO");
  }
}