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>
int chkmax(T& a, T b) {
  if (b > a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
int chkmin(T& a, T b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class iterator>
void output(iterator begin, iterator end, ostream& out = cerr) {
  while (begin != end) {
    out << (*begin) << " ";
    begin++;
  }
  out << endl;
}
template <class T>
void output(T x, ostream& out = cerr) {
  output(x.begin(), x.end(), out);
}
void fast_io() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
struct Hasher {
  map<vector<int>, int> dt;
  int ptr = 0;
  int getHash(const vector<int>& cur) {
    auto it = dt.find(cur);
    if (it == dt.end()) {
      return dt[cur] = ptr++;
    } else {
      return it->second;
    }
  }
};
vector<vector<vector<int>>> g;
vector<int> used, sz;
multiset<int> forests;
int n;
Hasher trees;
int hashRootedTree(int id, int v, int pv) {
  vector<int> children;
  for (auto v1 : g[id][v]) {
    if (v1 != pv) {
      children.push_back(hashRootedTree(id, v1, v));
    }
  }
  sort(children.begin(), children.end());
  return trees.getHash(children);
}
Hasher center;
void szDfs(int id, int v, int pv) {
  sz[v] = 1;
  for (auto v1 : g[id][v]) {
    if (v1 != pv) {
      szDfs(id, v1, v);
      sz[v] += sz[v1];
    }
  }
}
int centroid(int id, int v, int pv, int all_sz) {
  for (auto v1 : g[id][v]) {
    if (v1 == pv) {
      continue;
    }
    if (sz[v1] * 2 == all_sz) {
      vector<int> pp = {hashRootedTree(id, v, v1), hashRootedTree(id, v1, v)};
      if (pp[1] < pp[0]) {
        swap(pp[1], pp[0]);
      }
      return center.getHash(pp);
    }
    if (sz[v1] * 2 > all_sz) {
      return centroid(id, v1, v, all_sz);
    }
  }
  return center.getHash({hashRootedTree(id, v, v)});
}
int hashTree(int id, int v) {
  szDfs(id, v, v);
  int res = centroid(id, v, v, sz[v]);
  return res;
}
Hasher seq;
void printTree(int id) {
  for (int i = 0; i < n; ++i) {
    vector<int> out;
    for (auto v : g[id][i]) {
      out.push_back(v);
    }
    if (!out.empty()) {
      cerr << i << ":";
      for (auto v : out) {
        cerr << ' ' << v;
      }
      cerr << '\n';
    }
  }
}
int hashForest(int id) {
  vector<int> treeHashes;
  fill(used.begin(), used.end(), 0);
  for (int i = 0; i < n; ++i) {
    if (used[i] == 0) {
      treeHashes.push_back(hashTree(id, i));
    }
  }
  sort(treeHashes.begin(), treeHashes.end());
  int h = seq.getHash(vector<int>());
  for (auto h1 : treeHashes) {
    h = seq.getHash({h, h1});
  }
  return h;
}
int checkGraph(int id, int pivot) {
  multiset<int> cur = forests;
  for (int i = 0; i < n; ++i) {
    if (i != pivot) {
      for (int v = 0; v < n; ++v) {
        g[n][v].clear();
        if (v == i) {
          continue;
        }
        for (auto v1 : g[id][v]) {
          if (v1 != i) {
            g[n][v].push_back(v1);
          }
        }
      }
      int H = hashForest(n);
      auto it = cur.find(H);
      if (it == cur.end()) {
        return 0;
      }
      cur.erase(it);
    }
  }
  return 1;
}
void readGraph(int id) {
  int m;
  cin >> m;
  while (m--) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    g[id][u].push_back(v);
    g[id][v].push_back(u);
  }
}
int dfs(int id, int v, int pv) {
  used[v] = 1;
  for (auto v1 : g[id][v]) {
    if (used[v1] == 1 && v1 != pv) {
      return 1;
    }
    if (v1 != pv && dfs(id, v1, v)) {
      return 1;
    }
  }
  return 0;
}
int verifyGraph(int id) {
  fill(used.begin(), used.end(), 0);
  int isolatedCnt = 0, v0 = -1, cmpCnt = 0;
  for (int i = 0; i < n; ++i) {
    if (g[id][i].empty()) {
      isolatedCnt++;
      v0 = i;
      continue;
    }
    if (used[i] == 0) {
      if (dfs(id, i, i)) {
        return -2;
      }
      cmpCnt++;
    }
  }
  if (cmpCnt == 1 && isolatedCnt == 1) {
    return v0;
  } else {
    return -1;
  }
}
void solve() {
  cin >> n >> n;
  used.resize(n);
  sz.resize(n);
  g.assign(n + 1, vector<vector<int>>(n));
  int good_graph = -1, bad = 0, pivot = -1;
  for (int it = 0; it < n; ++it) {
    readGraph(it);
    int outcome = verifyGraph(it);
    if (outcome == -2) {
      bad = 1;
    }
    if (outcome >= 0) {
      pivot = outcome;
      good_graph = it;
    }
  }
  if (bad) {
    cout << "NO\n";
    return;
  }
  for (int i = 0; i < n; ++i) {
    if (i != good_graph) {
      forests.insert(hashForest(i));
    }
  }
  int yes = 0;
  for (int i = 0; i < n; ++i) {
    if (i != pivot) {
      g[good_graph][pivot].push_back(i);
      g[good_graph][i].push_back(pivot);
      if (checkGraph(good_graph, pivot)) {
        cout << "YES\n";
        yes = 1;
        for (int j = 0; j < n; ++j) {
          for (auto j1 : g[good_graph][j]) {
            if (j1 > j) {
              cout << j + 1 << ' ' << j1 + 1 << '\n';
            }
          }
        }
        break;
      }
      g[good_graph][pivot].pop_back();
      g[good_graph][i].pop_back();
    }
  }
  if (!yes) {
    cout << "NO\n";
  }
}
signed main() {
  fast_io();
  int T;
  cin >> T;
  while (T--) {
    solve();
  }
}