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;
template <class T>
bool uin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
const int maxn = 101;
vector<int> e[maxn][maxn];
int vis[maxn], w[maxn], maxch[maxn];
int n;
int forb;
void dfs(int t, int v, vector<int> &path) {
  if (vis[v]) return;
  vis[v] = 1;
  path.push_back(v);
  for (int u : e[t][v]) dfs(t, u, path);
}
vector<vector<int> > comps(int t) {
  vector<vector<int> > res;
  for (int i = 0; i < (int)(n); ++i) vis[i] = 0;
  for (int i = 0; i < (int)(n); ++i) {
    if (vis[i]) continue;
    vector<int> p;
    dfs(t, i, p);
    res.push_back(p);
  }
  return res;
}
map<vector<int>, int> types;
int getType(vector<int> v) {
  sort((v).begin(), (v).end());
  if (!types.count(v)) {
    int z = types.size();
    types[v] = z;
  }
  return types[v];
}
int dfsType(int t, int v, int p) {
  vector<int> z;
  if (v == forb) return getType(z);
  for (int u : e[t][v]) {
    if (u == forb || u == p) continue;
    z.push_back(dfsType(t, u, v));
  }
  return getType(z);
}
void dfsw(int t, int v, int p, vector<int> &path) {
  w[v] = 1;
  maxch[v] = 0;
  path.push_back(v);
  if (v == forb) return;
  for (int u : e[t][v]) {
    if (u == p || u == forb) continue;
    dfsw(t, u, v, path);
    w[v] += w[u];
    uax(maxch[v], w[u]);
  }
}
vector<int> getCentroids(int t, int v) {
  vector<int> path;
  dfsw(t, v, -1, path);
  vector<int> centrs;
  for (int u : path) {
    if (2 * maxch[u] <= w[v] && 2 * (w[v] - w[u]) <= w[v]) centrs.push_back(u);
  }
  assert(centrs.size() <= 2);
  for (int u : path) vis[u] = 1;
  return centrs;
}
int getForestType(int t) {
  for (int i = 0; i < (int)(n); ++i) vis[i] = 0;
  vector<int> v;
  for (int i = 0; i < (int)(n); ++i) {
    if (vis[i]) continue;
    vector<int> c = getCentroids(t, i);
    int T = 1e9;
    for (int u : c) {
      uin(T, dfsType(t, u, -1));
    }
    v.push_back(T);
  }
  return getType(v);
}
int ZZ;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;
  int Q;
  cin >> Q;
  while (Q-- > 0) {
    cin >> n >> n;
    for (int i = 0; i < (int)(n); ++i)
      for (int j = 0; j < (int)(n); ++j) e[i][j].clear();
    for (int i = 0; i < (int)(n); ++i) {
      int m;
      cin >> m;
      for (int j = 0; j < (int)(m); ++j) {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        e[i][x].push_back(y);
        e[i][y].push_back(x);
      }
    }
    forb = -1;
    vector<int> Z;
    for (int i = 0; i < (int)(n); ++i) Z.push_back(getForestType(i));
    ZZ = getType(Z);
    int b = 0;
    while (comps(b).size() != 2) ++b;
    vector<vector<int> > c = comps(b);
    if (c[0].size() != 1) swap(c[0], c[1]);
    assert(c[0].size() == 1);
    int X = c[0][0];
    bool done = false;
    for (int i = 0; i < (int)(n); ++i) {
      if (i == X) continue;
      e[b][i].push_back(X);
      e[b][X].push_back(i);
      vector<int> Y;
      for (int i = 0; i < (int)(n); ++i) {
        forb = i;
        Y.push_back(getForestType(b));
      }
      if (getType(Y) == ZZ) {
        cout << "YES\n";
        for (int i = 0; i < (int)(n); ++i)
          for (int j : e[b][i])
            if (i < j) cout << i + 1 << ' ' << j + 1 << '\n';
        done = true;
        break;
      }
      e[b][i].pop_back();
      e[b][X].pop_back();
    }
    if (!done) cout << "NO\n";
  }
  return 0;
}