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 long long MOD = (long long)1e9 + 7;
const long long P = 31;
long long add(long long x, long long y) {
  x += y;
  if (x >= MOD) return x - MOD;
  return x;
}
long long sub(long long x, long long y) {
  x -= y;
  if (x < 0) return x + MOD;
  return x;
}
long long mult(long long x, long long y) { return (x * y) % MOD; }
const int N = 111;
long long p[N];
pair<long long, int> multHashes(pair<long long, int> x,
                                pair<long long, int> y) {
  return make_pair(add(mult(x.first, p[y.second]), y.first),
                   x.second + y.second);
}
pair<long long, int> getVectorHash(vector<pair<long long, int> > a) {
  pair<long long, int> res = make_pair(0, 0);
  sort(a.begin(), a.end());
  for (pair<long long, int> x : a) res = multHashes(res, x);
  return res;
}
int n;
vector<int> G[N][N];
int ed[N];
vector<pair<long long, int> > initial_hashes;
bool used[N];
int sz[N];
vector<int> T[N];
vector<int> TT[N];
pair<long long, int> getTreeHash(int v, int par, vector<int> g[N]) {
  int deg = 1;
  vector<pair<long long, int> > a;
  for (int u : g[v]) {
    if (u == par) continue;
    deg++;
    a.push_back(getTreeHash(u, v, g));
  }
  return multHashes(make_pair(deg, 1), getVectorHash(a));
}
void dfs(int v, vector<int> g[N]) {
  used[v] = 1;
  sz[v] = 1;
  for (int u : g[v]) {
    if (used[u]) continue;
    dfs(u, g);
    sz[v] += sz[u];
  }
  return;
}
pair<int, int> getCentroids(vector<int> g[N], int v) {
  dfs(v, g);
  int u = v;
  while (true) {
    int w = -1;
    for (int x : g[u]) {
      if (sz[x] >= sz[u]) continue;
      if (2 * sz[x] > sz[v]) w = x;
    }
    if (w == -1) break;
    u = w;
  }
  int w = -1;
  for (int x : g[u]) {
    if (sz[x] >= sz[u]) continue;
    if (2 * sz[x] >= sz[v]) w = x;
  }
  if (w == -1) w = u;
  return make_pair(u, w);
}
pair<long long, int> getForestHash(vector<int> g[N]) {
  for (int i = 0; i < n; i++) {
    sz[i] = 0;
    used[i] = 0;
  }
  vector<pair<long long, int> > a;
  for (int v = 0; v < n; v++) {
    if (used[v]) continue;
    pair<int, int> cc = getCentroids(g, v);
    vector<pair<long long, int> > h;
    h.push_back(getTreeHash(cc.first, -1, g));
    h.push_back(getTreeHash(cc.second, -1, g));
    a.push_back(getVectorHash(h));
  }
  return getVectorHash(a);
}
void read() {
  scanf("%d%d", &n, &n);
  for (int it = 0; it < n; it++) {
    for (int i = 0; i < n; i++) G[it][i].clear();
    scanf("%d", &ed[it]);
    for (int i = 0; i < ed[it]; i++) {
      int v, u;
      scanf("%d%d", &v, &u);
      v--;
      u--;
      G[it][v].push_back(u);
      G[it][u].push_back(v);
    }
  }
  return;
}
bool acyclicDfs(int v, int par, vector<int> g[N]) {
  used[v] = 1;
  int parCnt = 0;
  for (int u : g[v]) {
    if (u == par) {
      parCnt++;
      if (parCnt > 1) return false;
      continue;
    }
    if (used[u]) return false;
    if (!acyclicDfs(u, v, g)) return false;
  }
  return true;
}
bool acyclic(vector<int> g[N]) {
  for (int i = 0; i < n; i++) used[i] = 0;
  for (int v = 0; v < n; v++) {
    if (used[v]) continue;
    if (!acyclicDfs(v, -1, g)) return false;
  }
  return true;
}
bool checkTree() {
  vector<pair<long long, int> > a;
  for (int it = 0; it < n; it++) {
    for (int v = 0; v < n; v++) {
      TT[v].clear();
      if (v == it) continue;
      for (int x : T[v])
        if (x != it) TT[v].push_back(x);
    }
    a.push_back(getForestHash(TT));
  }
  sort(a.begin(), a.end());
  return a == initial_hashes;
}
void printTree() {
  printf("YES\n");
  for (int v = 0; v < n; v++)
    for (int u : T[v])
      if (v < u) printf("%d %d\n", v + 1, u + 1);
  return;
}
bool solve2(int fId) {
  int v = -1;
  for (int i = 0; v == -1 && i < n; i++) {
    if (G[fId][i].empty()) v = i;
  }
  if (v == -1) return false;
  for (int u = 0; u < n; u++) {
    if (v == u) continue;
    for (int i = 0; i < n; i++) T[i] = G[fId][i];
    T[v].push_back(u);
    T[u].push_back(v);
    if (checkTree()) {
      printTree();
      return true;
    }
  }
  return false;
}
void solve() {
  read();
  for (int i = 0; i < n; i++) {
    if (ed[i] >= n - 1) {
      printf("NO\n");
      return;
    }
    if (!acyclic(G[i])) {
      printf("NO\n");
      return;
    }
  }
  int it = -1;
  for (int i = 0; i < n && it == -1; i++)
    if (ed[i] == n - 2) it = i;
  if (it == -1) {
    printf("NO\n");
    return;
  }
  initial_hashes.clear();
  for (int i = 0; i < n; i++) initial_hashes.push_back(getForestHash(G[i]));
  sort(initial_hashes.begin(), initial_hashes.end());
  if (!solve2(it)) printf("NO\n");
  return;
}
void init() {
  p[0] = 1;
  for (int i = 1; i < N; i++) p[i] = mult(p[i - 1], P);
  return;
}
int main() {
  init();
  int t;
  scanf("%d", &t);
  while (t--) solve();
  0;
}