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;
mt19937_64 rnd(52389794);
const unsigned long long key = rnd(), EPT = rnd();
class hashing {
 public:
  unsigned long long operator()(const unsigned long long &t) const {
    return t ^ key;
  }
};
unordered_map<unsigned long long, unsigned long long, hashing> mp, mp2;
unsigned long long gethash(unsigned long long v) {
  if (mp.find(v) == mp.end()) mp[v] = rnd();
  return mp[v];
}
unsigned long long gethash2(unsigned long long v) {
  if (mp2.find(v) == mp2.end()) mp2[v] = rnd();
  return mp2[v];
}
int T, n, K;
vector<int> stk;
void getchain(vector<int> *e, int np, int fath, vector<int> &ret, int ban = 0) {
  stk.push_back(np);
  if (stk.size() > ret.size()) ret = stk;
  for (int &x : e[np]) {
    if (x == fath || x == ban) continue;
    getchain(e, x, np, ret, ban);
  }
  stk.pop_back();
}
unsigned long long gethash(vector<int> *e, int np, int fath, bool *v,
                           int ban = 0) {
  unsigned long long r = 0;
  v[np] = 1;
  for (int &x : e[np]) {
    if (x == fath || x == ban) continue;
    r += gethash(e, x, np, v, ban);
  }
  return gethash(r);
}
unsigned long long gethash(vector<int> *e, int np, int fath, int ban = 0) {
  unsigned long long r = 0;
  for (int &x : e[np]) {
    if (x == fath || x == ban) continue;
    r += gethash(e, x, np, ban);
  }
  return gethash(r);
}
vector<int> v[110];
vector<unsigned long long> ths;
class treecast {
 public:
  int M, pos;
  vector<int> e[110];
  bool vis[110];
  vector<unsigned long long> hs;
  void init() {
    for (int i = 1; i <= n; i++) e[i].clear();
    hs.clear();
  }
  void geths() {
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) {
      if (i != pos && !vis[i]) {
        vector<int> cur;
        getchain(e, i, 0, cur);
        int r = cur.back();
        cur.clear();
        getchain(e, r, 0, cur);
        unsigned long long v1, v2;
        if (cur.size() & 1) {
          v1 = gethash(e, cur[cur.size() >> 1], 0, vis);
          v2 = EPT;
        } else {
          v1 = gethash(e, cur[cur.size() / 2 - 1], 0, vis);
          v2 = gethash(e, cur[cur.size() / 2], 0, vis);
        }
        hs.push_back(gethash2(v1 + v2));
      }
    }
    unsigned long long s = 0;
    for (unsigned long long &x : hs) s += x;
    ths.push_back(s);
  }
} h[110];
bool vis[110];
void solve() {
  scanf("%d%d", &n, &K);
  mp.clear();
  mp2.clear();
  ths.clear();
  for (int i = 1; i <= K; i++) {
    h[i].init();
    scanf("%d", &h[i].M);
    memset(vis, 0, sizeof(vis));
    for (int j = 0, a, b; j < h[i].M; j++) {
      scanf("%d%d", &a, &b);
      h[i].e[a].push_back(b);
      h[i].e[b].push_back(a);
      vis[a] = vis[b] = 1;
    }
    for (int j = 1; j <= n; j++) {
      if (!vis[j]) {
        h[i].pos = j;
        break;
      }
    }
  }
  int p = 0;
  for (int i = 1; i <= K; i++) {
    if (h[i].M == n - 2) {
      for (int j = 1; j <= n; j++) v[j] = h[i].e[j];
      p = h[i].pos;
      break;
    }
  }
  for (int i = 1; i <= K; i++) h[i].geths();
  sort(ths.begin(), ths.end());
  for (int i = 1; i <= n; i++) {
    if (i != p) {
      v[i].push_back(p);
      v[p].push_back(i);
      vector<unsigned long long> curhs;
      for (int j = 1; j <= n; j++) {
        unsigned long long s = 0;
        for (int &x : v[j]) {
          vector<int> cur;
          getchain(v, x, j, cur);
          int r = cur.back();
          cur.clear();
          getchain(v, r, j, cur, j);
          unsigned long long v1, v2;
          if (cur.size() & 1) {
            v1 = gethash(v, cur[cur.size() / 2], 0, j);
            v2 = EPT;
          } else {
            v1 = gethash(v, cur[cur.size() / 2 - 1], 0, j);
            v2 = gethash(v, cur[cur.size() / 2], 0, j);
          }
          s += gethash2(v1 + v2);
        }
        curhs.push_back(s);
      }
      sort(curhs.begin(), curhs.end());
      if (curhs == ths) {
        puts("YES");
        for (int j = 1; j <= n; j++) {
          for (int &x : v[j]) {
            if (x < j) printf("%d %d\n", x, j);
          }
        }
        return;
      }
      v[i].pop_back();
      v[p].pop_back();
    }
  }
  puts("NO");
}
int main() {
  scanf("%d", &T);
  while (T--) solve();
  return 0;
}