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>
template <typename T>
inline T max(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
inline T min(T a, T b) {
  return a < b ? a : b;
}
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline bool repr(T &a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline bool repl(T &a, T b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline T gcd(T a, T b) {
  T t;
  if (a < b) {
    while (a) {
      t = a;
      a = b % a;
      b = t;
    }
    return b;
  } else {
    while (b) {
      t = b;
      b = a % b;
      a = t;
    }
    return a;
  }
}
template <typename T>
inline T sqr(T x) {
  return x * x;
}
struct Cg {
  __attribute__((always_inline)) inline char operator()() { return getchar(); }
};
struct Cp {
  __attribute__((always_inline)) inline void operator()(char x) { putchar(x); }
};
__attribute__((always_inline)) inline bool IS(char x) {
  return x == 10 || x == 13 || x == ' ';
}
template <typename T>
struct Fr {
  T P;
  __attribute__((always_inline)) inline Fr &operator,(int &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator int() {
    int x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(long long &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator long long() {
    long long x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(char &x) {
    for (x = P(); IS(x); x = P())
      ;
    return *this;
  }
  __attribute__((always_inline)) inline operator char() {
    char x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(char *x) {
    char t = P();
    for (; IS(t); t = P())
      ;
    if (~t) {
      for (; !IS(t) && ~t; t = P()) *x++ = t;
    }
    *x++ = 0;
    return *this;
  }
  __attribute__((always_inline)) inline Fr &operator,(double &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (t == '.') {
      double u = 0.1;
      for (t = P(); t >= '0' && t <= '9'; t = P(), u *= 0.1) x += u * (t - '0');
    }
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator double() {
    double x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(long double &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (t == '.') {
      double u = 0.1;
      for (t = P(); t >= '0' && t <= '9'; t = P(), u *= 0.1) x += u * (t - '0');
    }
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator long double() {
    long double x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(unsigned int &x) {
    x = 0;
    unsigned char t = P();
    while (t < '0' || t > '9') t = P();
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    return *this;
  }
  __attribute__((always_inline)) inline operator unsigned int() {
    unsigned int x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(unsigned long long &x) {
    x = 0;
    unsigned char t = P();
    while (t < '0' || t > '9') t = P();
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    return *this;
  }
  __attribute__((always_inline)) inline operator unsigned long long() {
    unsigned long long x;
    *this, x;
    return x;
  }
};
Fr<Cg> in;
template <typename T>
struct Fw {
  T P;
  __attribute__((always_inline)) inline Fw &operator,(int x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(int x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(unsigned int x) {
    if (x) {
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(unsigned int x) {
    if (x) {
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(long long x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[19], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(long long x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[19], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(unsigned long long x) {
    if (x) {
      unsigned char s[20], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(unsigned long long x) {
    if (x) {
      unsigned char s[20], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(char x) {
    P(x);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(char x) {
    P(x);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(const char *x) {
    while (*x) P(*x++);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(const char *x) {
    while (*x) P(*x++);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(double x, int y) {
    if (y) {
      double t = 0.5;
      for (int i = y; i--;) t *= 0.1;
      if (x >= 0)
        x += t;
      else
        x -= t, P('-');
      *this, (long long)(abs(x));
      P('.');
      if (x < 0) x = -x;
      while (y--) {
        x *= 10;
        x -= floor(x * 0.1) * 10;
        P(((int)x) % 10 + '0');
      }
    } else if (x >= 0)
      *this, (long long)(x + 0.5);
    else
      *this, (long long)(x - 0.5);
    ;
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(long double x, int y) {
    if (y) {
      double t = 0.5;
      for (int i = y; i--;) t *= 0.1;
      if (x >= 0)
        x += t;
      else
        x -= t, P('-');
      *this, (long long)(abs(x));
      P('.');
      if (x < 0) x = -x;
      while (y--) {
        x *= 10;
        x -= floor(x * 0.1) * 10;
        P(((int)x) % 10 + '0');
      }
    } else if (x >= 0)
      *this, (long long)(x + 0.5);
    else
      *this, (long long)(x - 0.5);
    ;
    return *this;
  }
};
Fw<Cp> out;
const int N = 103;
unsigned long long hp[N * 2];
struct tree {
  std::vector<int> p[N];
  int n, m, tot, mi, wx, wy, fa[N], sz[N];
  bool vis[N];
  inline void clear() {
    for (int i = 1, iend = n; i <= iend; i++)
      p[i].clear(), fa[i] = sz[i] = vis[i] = 0;
    n = m = tot = mi = wx = wy = 0;
  }
  inline void read(int _n) {
    n = _n, m = in;
    for (int i = 1, iend = m; i <= iend; i++) {
      int x, y;
      in, x, y;
      p[x].push_back(y);
      p[y].push_back(x);
    }
  }
  inline void remove(int x) {
    p[x].clear();
    for (int i = 1, iend = n; i <= iend; i++) {
      std::vector<int> tmp;
      for (__typeof((p[i]).end()) j = (p[i]).begin(); j != (p[i]).end(); ++j)
        if (*j != x) tmp.push_back(*j);
      tmp.swap(p[i]);
    }
  }
  inline void dfs1(int x) {
    tot++;
    vis[x] = 1;
    sz[x] = 1;
    for (__typeof((p[x]).end()) i = (p[x]).begin(); i != (p[x]).end(); ++i)
      if (*i != fa[x]) {
        fa[*i] = x;
        dfs1(*i);
        sz[x] += sz[*i];
      }
  }
  inline void dfs2(int x) {
    int t = tot - sz[x];
    for (__typeof((p[x]).end()) i = (p[x]).begin(); i != (p[x]).end(); ++i)
      if (*i != fa[x]) dfs2(*i), repr(t, sz[*i]);
    if (t == mi)
      wy = x;
    else if (t < mi)
      mi = t, wx = x, wy = 0;
  }
  inline unsigned long long dfs3(int x, int fa) {
    std::vector<std::pair<unsigned long long, int> > q;
    sz[x] = 1;
    for (__typeof((p[x]).end()) i = (p[x]).begin(); i != (p[x]).end(); ++i)
      if (*i != fa) {
        q.push_back(std::make_pair(dfs3(*i, x), sz[*i]));
        sz[x] += sz[*i];
      }
    std::sort(q.begin(), q.end());
    unsigned long long res = 1;
    for (__typeof((q).end()) i = (q).begin(); i != (q).end(); ++i)
      res = res * hp[i->second * 2] + i->first;
    res = res * hp[1] + 2;
    return res;
  }
  inline unsigned long long gethash() {
    for (int i = 1, iend = n; i <= iend; i++) vis[i] = 0;
    std::vector<std::pair<unsigned long long, int> > q;
    for (int i = 1, iend = n; i <= iend; i++)
      if (!vis[i]) {
        fa[i] = 0;
        tot = 0;
        dfs1(i);
        mi = tot;
        dfs2(i);
        if (!wy) {
          q.push_back(std::make_pair(dfs3(wx, 0), tot));
        } else {
          assert(mi * 2 == tot);
          unsigned long long a = dfs3(wx, wy), b = dfs3(wy, wx);
          if (a > b) std::swap(a, b);
          a = ((3 * hp[tot] + a) * hp[tot] + b) * hp[1] + 4;
          q.push_back(std::make_pair(a, tot));
        }
      }
    std::sort(q.begin(), q.end());
    unsigned long long res = 5;
    for (__typeof((q).end()) i = (q).begin(); i != (q).end(); ++i)
      res = res * hp[i->second * 2] + i->first;
    res = res * hp[1] + 6;
    return res;
  }
} s[N], u, g, res;
int n;
unsigned long long hs[N], ht[N];
int main() {
  hp[0] = 1;
  for (int i = 1, iend = N * 2 - 1; i <= iend; i++)
    hp[i] = hp[i - 1] * 998244353;
  for (int T = in; T--;) {
    in, n, n;
    for (int i = 1, iend = n; i <= iend; i++) s[i].read(n);
    for (int i = 1, iend = n; i <= iend; i++) hs[i] = s[i].gethash();
    std::sort(hs + 1, hs + n + 1);
    for (int i = 1, iend = n; i <= iend; i++)
      if (s[i].m == n - 2) u = s[i];
    for (int i = 1, iend = n; i <= iend; i++)
      if (!u.p[i].size()) {
        for (int j = 1, jend = n; j <= jend; j++)
          if (j != i) {
            u.p[j].push_back(i);
            u.p[i].push_back(j);
            for (int k = 1, kend = n; k <= kend; k++) {
              g = u;
              g.remove(k);
              ht[k] = g.gethash();
            }
            std::sort(ht + 1, ht + n + 1);
            bool flag = 1;
            for (int i = 1, iend = n; i <= iend; i++) flag &= ht[i] == hs[i];
            if (flag) {
              res = u;
              break;
            }
            u.p[i].pop_back();
            u.p[j].pop_back();
          }
        break;
      }
    if (res.n) {
      out, "YES\n";
      for (int i = 1, iend = n; i <= iend; i++)
        for (__typeof((res.p[i]).end()) j = (res.p[i]).begin();
             j != (res.p[i]).end(); ++j)
          if (*j < i) out, i, ' ', *j, '\n';
    } else {
      out, "NO\n";
    }
    for (int i = 1, iend = n; i <= iend; i++) s[i].clear();
    u.clear(), g.clear(), res.clear();
  }
}