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;
struct node {
  unordered_map<int, int> ch;
  vector<int> term;
  int next(int v);
  int ins(int v);
};
pair<int, int> ed[105][105];
node trie[10005];
bool mark[105];
int last[105];
int pre[205];
int deg[105];
int vis[105];
int hv[105];
int hf[105];
int e[205];
int m[105];
int n, T, ec, c;
int node::next(int v) {
  if (ch.count(v))
    return ch[v];
  else
    return -1;
}
int node::ins(int v) {
  if (ch.count(v))
    return ch[v];
  else
    ch[v] = ++c;
  return c;
}
void add(int a, int b) {
  e[++ec] = b, pre[ec] = last[a], last[a] = ec;
  e[++ec] = a, pre[ec] = last[b], last[b] = ec;
}
int v[105];
void dfs_hash(int x, int par) {
  int i, k = 0;
  hf[x] = 23333;
  for (i = last[x]; i != 0; i = pre[i])
    if (e[i] != par) dfs_hash(e[i], x);
  for (i = last[x]; i != 0; i = pre[i])
    if (e[i] != par) v[++k] = hf[e[i]];
  sort(v + 1, v + k + 1);
  for (i = 1; i <= k; ++i)
    hf[x] = (((long long)hf[x] * 2333) ^ v[i]) % 1000000007;
  hf[x] = (long long)hf[x] * 4999 % 1000000007;
}
void calc_hash(int type) {
  int i;
  for (i = 1; i <= n; ++i)
    if (vis[i] == type) {
      memset(hf, 0, sizeof(hf));
      dfs_hash(i, 0);
      hv[i] = hf[i];
    }
}
void makehash(int p) {
  int i, k;
  memset(hv, 0, sizeof(hv));
  for (i = 1; i <= T; ++i) calc_hash(i);
  sort(hv + 1, hv + n + 1);
  k = 1;
  for (i = 1; i <= n; ++i) k = trie[k].ins(hv[i]);
  trie[k].term.push_back(p);
}
void buildtree(int ver) {
  int i;
  memset(last, 0, sizeof(last));
  memset(deg, 0, sizeof(deg));
  ec = 0;
  for (i = 1; i <= m[ver]; ++i) {
    add(ed[ver][i].first, ed[ver][i].second);
    ++deg[ed[ver][i].first], ++deg[ed[ver][i].second];
  }
}
void dfs(int x) {
  int i;
  vis[x] = T;
  for (i = last[x]; i != 0; i = pre[i])
    if (vis[e[i]] != T) dfs(e[i]);
}
void init() {
  int i, j;
  for (i = 1; i <= n; ++i) {
    buildtree(i), T = 0;
    memset(vis, 0, sizeof(vis));
    for (j = 1; j <= n; ++j)
      if (vis[j] == 0) {
        ++T;
        dfs(j);
      }
    makehash(i);
  }
}
int find() {
  int i, j = 1;
  for (i = 1; i <= n; ++i)
    if ((j = trie[j].next(hv[i])) == -1) return 0;
  return j;
}
bool check(int to, int nv, int del) {
  int i, p;
  m[n + 2] = 0;
  if (del != nv && del != to) ed[n + 2][++m[n + 2]] = make_pair(nv, to);
  for (i = 1; i <= m[n + 1]; ++i)
    if (ed[n + 1][i].first != del && ed[n + 1][i].second != del)
      ed[n + 2][++m[n + 2]] = ed[n + 1][i];
  memset(vis, 0, sizeof(vis));
  buildtree(n + 2);
  memset(hv, 0, sizeof(hv));
  calc_hash(0);
  sort(hv + 1, hv + n + 1);
  if ((p = find()) == 0) return 0;
  for (i = 0; i < trie[p].term.size(); ++i)
    if (!mark[trie[p].term[i]]) {
      mark[trie[p].term[i]] = 1;
      return 1;
    }
  return 0;
}
bool work() {
  int i, j, x, gr;
  for (i = 1; i <= n; ++i)
    if (m[i] == n - 2) break;
  buildtree(i);
  memcpy(ed[n + 1], ed[i], sizeof(ed[i]));
  m[n + 1] = m[i];
  for (i = 1; i <= n; ++i)
    if (deg[i] == 0) break;
  x = i;
  for (i = 1; i <= n; ++i)
    if (i != x) {
      memset(mark, 0, sizeof(mark));
      for (j = 1; j <= n; ++j)
        if (!check(i, x, j)) break;
      if (j > n) {
        ed[n + 1][++m[n + 1]] = make_pair(i, x);
        return 1;
      }
    }
  return 0;
}
void output() {
  int i;
  for (i = 1; i < n; ++i)
    printf("%d %d\n", ed[n + 1][i].first, ed[n + 1][i].second);
}
void spec2() {
  if (m[1] == 0 && m[2] == 0)
    printf("YES\n1 2\n");
  else
    printf("NO\n");
}
int main() {
  int i, j, t, x, y;
  scanf("%d", &t);
  while (t--) {
    while (c) {
      trie[c].ch.clear();
      trie[c].term.clear();
      --c;
    }
    c = 1;
    scanf("%d%d", &n, &n);
    for (i = 1; i <= n; ++i) {
      scanf("%d", &m[i]);
      for (j = 1; j <= m[i]; ++j) {
        scanf("%d%d", &x, &y);
        ed[i][j] = make_pair(x, y);
      }
    }
    if (n == 2) {
      spec2();
      continue;
    }
    init();
    if (work()) {
      printf("YES\n");
      output();
    } else
      printf("NO\n");
  }
  fclose(stdin);
  fclose(stdout);
  return 0;
}