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;
bool list_comp(list<int> l1, list<int> l2) {
  for (list<int>::iterator it1 = l1.begin(), it2 = l2.begin();
       it1 != l1.end() && it2 != l2.end(); it1++, it2++) {
    if (*(it1) != *(it2)) {
      return *(it1) < *(it2);
    }
  }
  return false;
}
class Forest {
 public:
  int vsize;
  vector<int> v[110];
  int d[110];
  vector<pair<int, int> > roots;
  int parents[110];
  vector<int> sons[110];
  int weights[110];
  int visited[110];
  bool deleted[110];
  int num_deleted;
  Forest() { Forest(110 - 1); }
  Forest(int n) {
    vsize = 0;
    num_deleted = 0;
    for (int i = 1; i <= n; i++) {
      d[i] = 0;
      deleted[i] = false;
    }
  }
  void markDeleted(int node) {
    if (!deleted[node]) deleted[node] = true;
    vsize--;
    num_deleted++;
  }
  void markUndeleted(int node) {
    if (deleted[node]) deleted[node] = false;
    vsize++;
    num_deleted--;
  }
  int weightTree(int root) {
    visited[root] = true;
    int weight = 0, node;
    for (int i = 0; i < v[root].size(); i++) {
      node = v[root][i];
      if (!visited[node] && !deleted[node]) {
        weight += weightTree(node);
      }
    }
    weights[root] = weight + 1;
    return weights[root];
  }
  void shift(int root, int new_root) {
    weights[root] -= weights[new_root];
    weights[new_root] += weights[root];
  }
  pair<int, int> findGravityRoot(int root) {
    int curr = root, adj;
    int weight = weightTree(root);
    bool done = false;
    while (!done) {
      done = true;
      for (int i = 0; i < v[curr].size(); i++) {
        adj = v[curr][i];
        if (deleted[adj]) continue;
        if (weights[adj] == weight / 2) {
          return make_pair(curr, adj);
        }
        if (weights[adj] > weight / 2) {
          done = false;
          shift(curr, adj);
          curr = adj;
          break;
        }
      }
    }
    return make_pair(curr, 0);
  }
  void labelParentSons(int root) {
    for (int i = 1; i <= vsize + num_deleted; i++) {
      visited[i] = false;
    }
    labelParentSonsHelp(root);
  }
  void labelParentSonsHelp(int root) {
    sons[root].clear();
    visited[root] = true;
    int node;
    for (int i = 0; i < v[root].size(); i++) {
      node = v[root][i];
      if (!visited[node] && !deleted[node]) {
        sons[root].push_back(node);
        parents[node] = root;
        labelParentSonsHelp(node);
      }
    }
  }
  void findTreeRoots() {
    roots.clear();
    for (int i = 1; i <= vsize + num_deleted; i++) {
      visited[i] = false;
    }
    pair<int, int> root;
    for (int i = 1; i <= vsize + num_deleted; i++) {
      if (!visited[i] && !deleted[i]) {
        root = findGravityRoot(i);
        roots.push_back(root);
      }
    }
  }
  void rootTreeIso(list<int> *rep) {
    vector<list<int> > sub_lists;
    for (int i = 0; i < roots.size(); i++) {
      list<int> new_list;
      sub_lists.push_back(new_list);
      if (roots[i].second == 0) {
        labelParentSons(roots[i].first);
        rootTreeIsoHelp(roots[i].first, &sub_lists[i]);
      } else {
        vector<list<int> > centers;
        centers.resize(2);
        labelParentSons(roots[i].first);
        rootTreeIsoHelp(roots[i].first, &centers[0]);
        labelParentSons(roots[i].second);
        rootTreeIsoHelp(roots[i].second, &centers[1]);
        spliceSubLists(centers, &sub_lists[i]);
      }
    }
    spliceSubLists(sub_lists, rep);
    rep->push_front(roots.size());
  }
  void rootTreeIsoHelp(int root, list<int> *rep) {
    int size = sons[root].size();
    if (size == 0) {
      rep->push_front(0);
      return;
    }
    vector<list<int> > sub_lists;
    for (int i = 0; i < size; i++) {
      list<int> new_list;
      sub_lists.push_back(new_list);
      rootTreeIsoHelp(sons[root][i], &sub_lists[i]);
    }
    spliceSubLists(sub_lists, rep);
    rep->push_front(size);
  }
  void spliceSubLists(vector<list<int> > &sub_lists, list<int> *sort_combine) {
    sort(sub_lists.begin(), sub_lists.end(), list_comp);
    int size = sub_lists.size();
    for (int i = 0; i < size; i++) {
      sort_combine->splice(sort_combine->end(), sub_lists[i]);
    }
  }
  void convertListToString(list<int> &l, string &s) {
    stringstream ss;
    for (list<int>::iterator it = l.begin(); it != l.end(); it++) {
      if (it == l.begin()) {
        ss << *(it);
      } else {
        ss << "," << *(it);
      }
    }
    s = ss.str();
  }
  void forestIsoHash(string &s) {
    findTreeRoots();
    list<int> rep;
    rootTreeIso(&rep);
    list<int>::iterator begin, it;
    int c = 0;
    begin = rep.begin();
    it = begin;
    it++;
    while (it != rep.end() && *(it) == 0) {
      c++;
      it = rep.erase(it);
    }
    *(begin) -= c;
    convertListToString(rep, s);
    if (0) cout << s << endl;
  }
  void parseForest(int numEdges) {
    int x, y;
    unordered_map<int, int> vmap;
    int label = 1;
    for (int i = 1; i <= numEdges; i++) {
      cin >> x >> y;
      if (vmap[x] == 0) {
        vmap[x] = label;
        label++;
      }
      if (vmap[y] == 0) {
        vmap[y] = label;
        label++;
      }
      x = vmap[x];
      y = vmap[y];
      addEdge(x, y);
    }
  }
  void addEdge(int x, int y) {
    if (v[x].size() == 0) {
      vsize++;
    }
    if (v[y].size() == 0) {
      vsize++;
    }
    v[x].push_back(y);
    v[y].push_back(x);
    d[x]++;
    d[y]++;
  }
  void removePrevEdge(int x, int y) {
    v[x].pop_back();
    v[y].pop_back();
    if (v[x].size() == 0) {
      vsize--;
    }
    if (v[y].size() == 0) {
      vsize--;
    }
    d[x]--;
    d[y]--;
  }
  void printRootedTree(int root) {
    labelParentSons(root);
    printRootedTreeHelp(root);
  }
  void printRootedTreeHelp(int root) {
    int adj;
    for (int i = 0; i < sons[root].size(); i++) {
      adj = sons[root][i];
      cout << root << " " << adj << endl;
      printRootedTreeHelp(adj);
    }
  }
};
int find2P(int start, Forest &t) {
  int next;
  int count = 0;
  for (int i = 0; i < t.v[start].size(); i++) {
    next = t.v[start][i];
    count += t.v[next].size() - 1;
  }
  return count;
}
void solveEasy() {
  int n, ans = 0;
  cin >> n;
  Forest t1(n);
  t1.parseForest(n - 1);
  for (int i = 1; i <= n; i++) {
    ans += find2P(i, t1);
  }
  cout << ans / 2 << endl;
}
void freeMemory(vector<Forest *> &trees) {
  while (trees.size()) {
    delete trees[trees.size() - 1];
    trees.pop_back();
  }
}
void solveMedium(vector<Forest *> &trees) {
  int n, k;
  cin >> n >> k;
  if (0) cout << "N is " << n << " K is " << k << endl;
  int m;
  int totalDegree = 0;
  int index = -1;
  string s;
  unordered_map<string, int> hm, hmcmp;
  for (int i = 0; i < n; i++) {
    cin >> m;
    trees.push_back(new Forest(n));
    trees[i]->parseForest(m);
    if (0) {
      cout << "vsize: " << trees[i]->vsize
           << " roots: " << trees[i]->roots.size() << " ";
    }
    trees[i]->forestIsoHash(s);
    hm[s]++;
    if (trees[i]->vsize == n - 1 && trees[i]->roots.size() == 1) {
      index = i;
    }
    totalDegree += (n - m - 1);
  }
  if (0) cout << "index: " << index << endl;
  if (0) cout << "totalDegree: " << totalDegree << endl;
  if (n == 2) {
    if (trees[0]->roots.size() != 0 || trees[1]->roots.size() != 0) {
      cout << "NO" << endl;
    } else {
      cout << "YES"
           << "\n"
           << "1 2" << endl;
    }
    return;
  }
  if (index == -1) {
    cout << "NO" << endl;
    return;
  }
  if (totalDegree != 2 * (n - 1)) {
    cout << "NO" << endl;
    return;
  }
  Forest *t = trees[index];
  if (0) cout << "initial T: " << endl;
  t->forestIsoHash(s);
  int nv;
  nv = n;
  bool found;
  for (int i = 1; i <= n - 1; i++) {
    t->addEdge(nv, i);
    if (0) {
      cout << "after adding to " << i << ": ";
      t->forestIsoHash(s);
    }
    found = true;
    for (int j = 1; j <= n; j++) {
      t->markDeleted(j);
      t->forestIsoHash(s);
      t->markUndeleted(j);
      int x = ++hmcmp[s];
      if (hm[s] < x) {
        found = false;
        break;
      }
    }
    if (found) {
      cout << "YES" << endl;
      t->printRootedTree(t->roots[0].first);
      return;
    }
    t->removePrevEdge(nv, i);
    if (0) {
      cout << "after remove " << i << ": ";
      t->forestIsoHash(s);
    }
    hmcmp.clear();
  }
  cout << "NO" << endl;
}
int main() {
  int z, n, k;
  vector<Forest *> trees;
  cin >> z;
  ;
  for (int i = 0; i < z; i++) {
    solveMedium(trees);
    freeMemory(trees);
  }
}