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 long long P = 1000 * 1000 + 3, Q = 1000 * 1000 * 1000 + 9, K = 315;
struct forest {
  vector<vector<int> > tree;
  vector<bool> used;
  vector<int> parent;
  int badVerticle;
  int n;
  void addEdge(int u, int v) {
    tree[u].push_back(v);
    tree[v].push_back(u);
  }
  void dfs(int v) {
    used[v] = true;
    for (int i = 0; i < (int)tree[v].size(); i++) {
      int to = tree[v][i];
      if (!used[to] && to != badVerticle) {
        parent[to] = v;
        dfs(to);
      }
    }
  }
  pair<int, int> dfsLongest(int v, int h) {
    used[v] = true;
    pair<int, int> res = make_pair(h, v);
    for (int i = 0; i < (int)tree[v].size(); i++) {
      int to = tree[v][i];
      if (!used[to] && to != badVerticle) {
        res = max(res, dfsLongest(to, h + 1));
      }
    }
    return res;
  }
  forest(int _n) {
    badVerticle = -1;
    n = _n;
    tree.resize(n + 2);
    used.resize(n + 2);
    parent.resize(n + 2);
  }
  forest() {}
  bool isConnected() {
    for (int i = 1; i <= n; i++) {
      used[i] = false;
    }
    dfs(1);
    for (int i = 1; i <= n; i++) {
      if (!used[i] && i != badVerticle) {
        return false;
      }
    }
    return true;
  }
  pair<int, int> getCenters(int v) {
    for (int i = 1; i <= n; i++) {
      used[i] = false;
    }
    pair<int, int> a = dfsLongest(v, 0);
    for (int i = 1; i <= n; i++) {
      used[i] = false;
    }
    pair<int, int> b = dfsLongest(a.second, 0);
    for (int i = 1; i <= n; i++) {
      used[i] = false;
    }
    dfs(a.second);
    int j = b.second;
    pair<int, int> res = make_pair(-1, -1);
    int dist1 = 0, dist2 = b.first;
    while (j != a.second) {
      if (abs(dist1 - dist2) <= 1) {
        if (res.first == -1) {
          res.first = j;
        } else {
          res.second = j;
        }
      }
      dist1++;
      dist2--;
      j = parent[j];
    }
    if (a.second == b.second) {
      res.first = a.second;
    }
    if (res.second == -1) res.second = res.first;
    return res;
  }
  long long calcHash(int v) {
    used[v] = true;
    vector<long long> go;
    for (int i = 0; i < (int)tree[v].size(); i++) {
      int to = tree[v][i];
      if (!used[to] && to != badVerticle) {
        go.push_back(calcHash(to));
      }
    }
    sort(go.begin(), go.end());
    long long res = 0;
    for (int i = 0; i < (int)go.size(); i++) {
      res = (res * P + go[i]) % Q;
    }
    res = (res * P + K) % Q;
    return res;
  }
  long long calcHashRoot(int root) {
    pair<int, int> centers = getCenters(root);
    for (int i = 1; i <= n; i++) {
      used[i] = false;
    }
    long long h1 = calcHash(centers.first);
    for (int i = 1; i <= n; i++) {
      used[i] = false;
    }
    long long h2 = calcHash(centers.second);
    if (h1 > h2) swap(h1, h2);
    long long res = 0;
    res = (res * P + h1) % Q;
    res = (res * P + h2) % Q;
    res = (res + K) % Q;
    return res;
  }
  long long calcTotalHash() {
    vector<int> roots;
    for (int i = 1; i <= n; i++) {
      used[i] = false;
    }
    for (int i = 1; i <= n; i++) {
      if (!used[i] && i != badVerticle) {
        roots.push_back(i);
        dfs(i);
      }
    }
    vector<long long> go;
    for (int i = 0; i < (int)roots.size(); i++) {
      go.push_back(calcHashRoot(roots[i]));
    }
    sort(go.begin(), go.end());
    long long res = 0;
    for (int i = 0; i < (int)go.size(); i++) {
      res = (res * P + go[i]) % Q;
    }
    res = (res * P + K) % Q;
    return res;
  }
  void findBad() {
    for (int i = 1; i <= n; i++) {
      if ((int)tree[i].size() == 0) {
        badVerticle = i;
      }
    }
  }
};
const int MAXN = 107;
forest f[MAXN];
long long hashs[MAXN];
int main() {
  int q;
  scanf("%d", &q);
  for (int qq = 0; qq < q; qq++) {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
      f[i] = forest(n);
      int m;
      scanf("%d", &m);
      for (int j = 1; j <= m; j++) {
        int u, v;
        scanf("%d %d", &u, &v);
        f[i].addEdge(u, v);
      }
      f[i].findBad();
    }
    int baseTree = -1;
    for (int i = 1; i <= n; i++) {
      if (f[i].isConnected()) {
        baseTree = i;
      }
      hashs[i] = f[i].calcTotalHash();
    }
    sort(hashs + 1, hashs + 1 + n);
    assert(baseTree != -1);
    bool solved = false;
    for (int parent = 1; parent <= n; parent++) {
      forest go = f[baseTree];
      if (parent == go.badVerticle) {
        continue;
      }
      go.addEdge(go.badVerticle, parent);
      go.badVerticle = -1;
      vector<long long> goHashs;
      for (int i = 1; i <= n; i++) {
        go.badVerticle = i;
        goHashs.push_back(go.calcTotalHash());
      }
      sort(goHashs.begin(), goHashs.end());
      bool ok = true;
      for (int i = 0; i < (int)goHashs.size(); i++) {
        if (goHashs[i] != hashs[i + 1]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        printf("YES\n");
        for (int i = 1; i <= n; i++) {
          for (int j = 0; j < (int)go.tree[i].size(); j++) {
            int to = go.tree[i][j];
            if (i < to) {
              printf("%d %d\n", i, to);
            }
          }
        }
        solved = true;
      }
      if (solved) break;
    }
    if (!solved) {
      printf("NO\n");
    }
  }
}