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 int NMOD = 2;
const int MOD[NMOD] = {1000000007, 1000000009};
struct hs {
  int hv[NMOD];
  int lp[NMOD];
  hs() {
    for (int i = (0); i < (NMOD); i++) hv[i] = 0, lp[i] = 1;
  }
  bool operator<(const hs &o) const {
    for (int i = (0); i < (NMOD); i++)
      if (hv[i] != o.hv[i]) return hv[i] < o.hv[i];
    return false;
  }
  bool operator==(const hs &o) const {
    for (int i = (0); i < (NMOD); i++)
      if (hv[i] != o.hv[i]) return false;
    return true;
  }
  bool operator!=(const hs &o) const { return !(*this == o); }
};
hs nd;
hs delim1;
hs delim2;
hs mrg(hs a, hs b) {
  for (int i = (0); i < (NMOD); i++) {
    a.hv[i] = (a.hv[i] * 1ll * b.lp[i] + b.hv[i]) % MOD[i];
    a.lp[i] = a.lp[i] * 1ll * b.lp[i] % MOD[i];
  }
  return a;
}
struct HTREE {
  int n;
  vector<int> u[1005];
  map<int, hs> cache[1005];
  int l[1005];
  set<hs> hshs;
  int gl(int i) { return i == l[i] ? i : l[i] = gl(l[i]); }
  void init(int _n) {
    n = _n;
    for (int i = (0); i < (n); i++) cache[i].clear(), u[i].clear();
    for (int i = (0); i < (n); i++) l[i] = i;
    hshs.clear();
  }
  void adde(int i, int j) {
    u[i].push_back(j);
    u[j].push_back(i);
    l[gl(i)] = gl(j);
  }
  hs dp(int i, int j) {
    if (cache[i].count(j)) return cache[i][j];
    vector<hs> v;
    for (int k : u[j])
      if (k != i) {
        v.push_back(dp(j, k));
      }
    sort(v.begin(), v.end());
    hs res = delim1;
    for (auto h : v) {
      res = mrg(res, h);
    }
    res = mrg(res, delim2);
    cache[i][j] = res;
    return cache[i][j];
  }
  void proc() {
    for (int i = (0); i < (n); i++) cache[i].clear();
    hshs.clear();
    for (int i = (0); i < (n); i++) {
      vector<hs> v;
      for (int j : u[i])
        if (j != i) {
          v.push_back(dp(i, j));
        }
      sort(v.begin(), v.end());
      hs res = delim1;
      for (auto h : v) {
        res = mrg(res, h);
      }
      res = mrg(res, delim2);
      hshs.insert(res);
    }
  }
};
HTREE ht[105];
int cnt[105];
int main() {
  for (int i = (0); i < (2); i++) nd.hv[i] = 1, nd.lp[i] = 137;
  for (int i = (0); i < (2); i++) delim1.hv[i] = 2, delim1.lp[i] = 137;
  for (int i = (0); i < (2); i++) delim2.hv[i] = 3, delim2.lp[i] = 137;
  int T;
  scanf("%d", &T);
  for (int _ = (0); _ < (T); _++) {
    int n, k;
    scanf("%d %d", &n, &k);
    int sp = -1, spi = -1;
    for (int i = (0); i < (k); i++) {
      int m;
      scanf("%d", &m);
      ht[i].init(n);
      for (int j = (0); j < (m); j++) {
        int x, y;
        scanf("%d %d", &x, &y);
        x--;
        y--;
        ht[i].adde(x, y);
      }
      for (int j = (0); j < (n); j++) cnt[j] = 0;
      for (int j = (0); j < (n); j++) cnt[ht[i].gl(j)]++;
      set<int> lds;
      for (int j = (0); j < (n); j++) lds.insert(ht[i].gl(j));
      if (int(lds.size()) == 2) {
        for (int j = (0); j < (n); j++) {
          if (cnt[j] == 1) {
            sp = i;
            spi = j;
          }
        }
      }
    }
    assert(sp != -1);
    swap(ht[sp], ht[0]);
    for (int i = (0); i < (k); i++) ht[i].proc();
    for (int z = (0); z < (n); z++)
      if (z != spi) {
        HTREE cnd = ht[0];
        cnd.adde(z, spi);
        cnd.proc();
        set<int> rem;
        for (int i = (0); i < (k); i++) rem.insert(i);
        for (int i = (0); i < (n); i++) {
          int brm = -1;
          for (int x : rem) {
            for (int j : cnd.u[i]) {
              if (!ht[x].hshs.count(cnd.dp(i, j))) {
                goto notfound;
              }
            }
            brm = x;
          notfound:;
          }
          if (brm == -1) {
            goto notgoodcand;
          } else {
            rem.erase(brm);
          }
        }
        printf("YES\n");
        for (int i = (0); i < (n); i++)
          for (int j : cnd.u[i])
            if (i < j) {
              printf("%d %d\n", i + 1, j + 1);
            }
        goto foundans;
      notgoodcand:;
      }
    printf("NO\n");
  foundans:;
  }
}