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 N = 101, P[] = {(int)1e9 + 7, (int)1e9 + 9};
int rd[2][N], hs[2][N];
int i, j, n, m, st, sum, f1, f2, D;
int c[N], v[N], sz[N], F[N];
vector<int> g[N];
vector<pair<int, int> > Pic[N];
vector<vector<int> > Hashmap;
int myrand(int j) {
  return (((long long)rand() << 32 ^ (long long)rand() << 16 ^ rand()) % P[j] +
          P[j]) %
         P[j];
}
void Initial() {
  for (i = 0; i <= 1; i++)
    for (j = 1; j < N; j++) rd[i][j] = myrand(i);
}
void dfs1(int x, int fa) {
  v[x] = sz[x] = 1;
  for (auto y : g[x])
    if (y != fa && y != D) dfs1(y, x), sz[x] += sz[y];
}
void dfs2(int x, int fa) {
  F[x] = sum - sz[x];
  for (auto y : g[x])
    if (y != fa && y != D) dfs2(y, x), F[x] = max(F[x], sz[y]);
  if (F[x] < F[f1])
    f1 = x;
  else if (F[x] < F[f2])
    f2 = x;
}
void dfs3(int x, int fa) {
  sz[x] = 1;
  for (auto y : g[x])
    if (y != fa && y != D) dfs3(y, x), sz[x] += sz[y];
  for (int t = 0; t <= 1; t++) hs[t][x] = 1;
  for (auto y : g[x])
    if (y != fa && y != D)
      for (int t = 0; t <= 1; t++)
        hs[t][x] = 1LL * hs[t][x] * (rd[t][sz[x]] + hs[t][y]) % P[t];
}
vector<int> solve(int x) {
  dfs1(x, 0);
  sum = sz[x];
  F[0] = 1 << 30;
  f1 = f2 = 0;
  dfs2(x, 0);
  vector<int> tmp;
  if (F[f1] != F[f2]) {
    dfs3(f1, 0);
    for (int t = 0; t <= 1; t++) tmp.push_back(hs[t][f1]);
    assert(tmp[0] != 0);
    return tmp;
  }
  dfs3(f1, f2);
  dfs3(f2, f1);
  int tot = sz[f1] + sz[f2];
  for (int t = 0; t <= 1; t++)
    tmp.push_back(1LL * (hs[t][f1] + rd[t][tot]) * (hs[t][f2] + rd[t][tot]) %
                  P[t]);
  assert(tmp[0] != 0);
  return tmp;
}
vector<int> check(int k) {
  int i, wh = 0;
  for (i = 1; i <= n; i++) v[i] = c[i] = 0;
  for (auto p : Pic[k]) c[p.first]++, c[p.second]++;
  for (i = 1; i <= n; i++)
    if (c[i] == 0) wh = i;
  if (Pic[k].size() == n - 2 && m == -1) m = k, st = wh;
  for (i = 1; i <= n; i++) g[i].clear();
  for (auto p : Pic[k])
    if (p.first != D && p.second != D)
      g[p.first].push_back(p.second), g[p.second].push_back(p.first);
  vector<vector<int> > All;
  assert(All.size() == 0);
  for (i = 1; i <= n; i++)
    if (!v[i]) All.push_back(solve(i));
  sort(All.begin(), All.end());
  vector<int> tmp;
  tmp.push_back(1);
  tmp.push_back(1);
  assert(tmp.size() == 2);
  for (auto p : All)
    for (int t = 0; t <= 1; t++) tmp[t] = 1LL * tmp[t] * p[t] % P[t];
  return tmp;
}
void work() {
  int i, wh = 0;
  Hashmap.clear();
  m = D = -1;
  for (i = 1; i <= n; i++) Hashmap.push_back(check(i));
  assert(m != -1);
  sort(Hashmap.begin(), Hashmap.end());
  vector<int> ans;
  for (i = 1; i <= n; i++) {
    if (i == st) continue;
    Pic[m].push_back({i, st});
    int flag = 0;
    for (D = 1; D <= n; D++) {
      vector<int> tmp = check(m);
      if (!binary_search(Hashmap.begin(), Hashmap.end(), tmp)) {
        flag = 1;
        break;
      }
    }
    if (flag == 0) wh = i;
    Pic[m].pop_back();
  }
  if (wh == 0) {
    printf("NO\n");
    return;
  }
  Pic[m].push_back({wh, st});
  printf("YES\n");
  for (auto p : Pic[m]) printf("%d %d\n", p.first, p.second);
}
int main() {
  Initial();
  int Case;
  scanf("%d", &Case);
  while (Case--) {
    scanf("%d%d", &n, &n);
    for (i = 1; i <= n; i++) {
      Pic[i].clear();
      scanf("%d", &m);
      for (j = 1; j <= m; j++) {
        int x, y;
        scanf("%d%d", &x, &y);
        Pic[i].push_back({x, y});
      }
    }
    work();
  }
}