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 inf = 1e9 + 7;
string to_string(string s) { return '"' + s + '"'; }
string to_string(char s) { return string(1, s); }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A>
string to_string(A);
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool f = 1;
  string r = "{";
  for (const auto& x : v) {
    if (!f) r += ", ";
    f = 0;
    r += to_string(x);
  }
  return r + "}";
}
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << " " << to_string(H);
  debug_out(T...);
}
int X[111];
int sub[111];
void dfs(const vector<vector<int>>& g, int u, int p) {
  sub[u] = 1;
  for (int v : g[u])
    if (v != p) {
      dfs(g, v, u);
      sub[u] += sub[v];
    }
}
pair<int, int> centroid(const vector<vector<int>>& g, int u, int p, int no) {
  for (int v : g[u])
    if (v != p) {
      if (sub[v] > no / 2) return centroid(g, v, u, no);
    }
  int c2 = u;
  for (int v : g[u])
    if (v != p) {
      if (no - sub[v] <= no / 2) c2 = v;
    }
  return {u, c2};
}
int get(const vector<vector<int>>& g, int u, int p) {
  vector<int> yo;
  for (int v : g[u])
    if (v != p) {
      yo.emplace_back(get(g, v, u));
    }
  sort((yo).begin(), (yo).end());
  int h = X[110];
  for (auto i = (0); i <= (int(yo.size()) - 1); ++i) {
    h ^= ((yo[i] * 1LL * X[i]) % inf);
  }
  return h;
}
pair<int, int> hsh(vector<pair<int, int>> a) {
  int h1 = X[110], h2 = X[110];
  sort((a).begin(), (a).end());
  for (auto i = (0); i <= (int(a.size()) - 1); ++i) {
    h1 ^= ((a[i].first * 1LL * X[i]) % inf);
    h2 ^= ((a[i].second * 1LL * X[i]) % inf);
  }
  return {h1, h2};
}
pair<int, int> hsh(const vector<vector<int>>& g) {
  int n = int(g.size());
  vector<int> vis(n);
  vector<pair<int, int>> H;
  for (auto i = (0); i <= (n - 1); ++i)
    if (!vis[i]) {
      stack<int> st;
      st.push(i);
      int x = 0, no = 0;
      vis[i] = 1;
      while (!st.empty()) {
        int u = st.top();
        st.pop();
        x += int(g[u].size()), no++;
        for (int v : g[u])
          if (!vis[v]) {
            vis[v] = 1;
            st.push(v);
          }
      }
      if (x != 2 * (no - 1)) {
        return {-1, -1};
      }
      dfs(g, i, -1);
      pair<int, int> c = centroid(g, i, -1, sub[i]);
      int h1 = get(g, c.first, c.second);
      int h2 = c.second != c.first ? get(g, c.second, c.first) : X[105];
      if (h1 > h2) swap(h1, h2);
      H.emplace_back(h1, h2);
    }
  return hsh(H);
}
int conn(const vector<vector<int>>& g) {
  int n = int(g.size());
  vector<int> vis(n);
  int r = -1;
  for (auto i = (0); i <= (n - 1); ++i)
    if (!g[i].empty()) r = i;
  if (r == -1) return n == 2 ? 0 : -1;
  vis[r] = 1;
  stack<int> st;
  st.push(r);
  int x = 0;
  while (!st.empty()) {
    int u = st.top();
    st.pop();
    ++x;
    for (int v : g[u])
      if (!vis[v]) {
        vis[v] = 1;
        st.push(v);
      }
  }
  if (x != n - 1) return -1;
  for (auto i = (0); i <= (n - 1); ++i)
    if (!vis[i]) return i;
  while (1)
    ;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  for (auto i = (0); i <= (110); ++i)
    X[i] = abs(rand() * 1LL * rand() * 1LL * rand() * 1LL * rand()) % inf;
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<vector<vector<int>>> g(k, vector<vector<int>>(n));
    vector<pair<int, int>> org;
    bool cant = 0;
    for (auto i = (0); i <= (k - 1); ++i) {
      int x;
      cin >> x;
      for (auto j = (1); j <= (x); ++j) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[i][a].push_back(b), g[i][b].push_back(a);
      }
      org.emplace_back(hsh(g[i]));
      if (org.back().first == -1) {
        cant = 1;
      }
    }
    bool done = 0;
    if (!cant) {
      pair<int, int> yo = hsh(org);
      for (auto i = (0); i <= (k - 1); ++i) {
        int l = conn(g[i]);
        if (l == -1) continue;
        for (auto j = (0); j <= (n - 1); ++j)
          if (j != l) {
            g[i][l].push_back(j), g[i][j].push_back(l);
            {
              vector<pair<int, int>> now;
              for (auto u = (0); u <= (n - 1); ++u) {
                vector<int> tmp = g[i][u];
                for (int v : tmp) {
                  g[i][u].erase(find((g[i][u]).begin(), (g[i][u]).end(), v));
                  g[i][v].erase(find((g[i][v]).begin(), (g[i][v]).end(), u));
                }
                now.emplace_back(hsh(g[i]));
                for (int v : tmp) {
                  g[i][u].push_back(v), g[i][v].push_back(u);
                }
              }
              if (hsh(now) == yo) {
                cout << "YES\n";
                for (auto u = (0); u <= (n - 1); ++u)
                  for (int v : g[i][u])
                    if (u < v) cout << u + 1 << " " << v + 1 << "\n";
                done = 1;
                break;
              }
            }
            g[i][l].erase(find((g[i][l]).begin(), (g[i][l]).end(), j));
            g[i][j].erase(find((g[i][j]).begin(), (g[i][j]).end(), l));
          }
        break;
      }
    }
    if (!done) cout << "NO\n";
  }
  return 0;
}