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;
template <class T>
int getbit(T s, int i) {
  return (s >> i) & 1;
}
template <class T>
T onbit(T s, int i) {
  return s | (T(1) << i);
}
template <class T>
T offbit(T s, int i) {
  return s & (~(T(1) << i));
}
template <class T>
int cntbit(T s) {
  return __builtin_popcount(s);
}
template <class T>
T gcd(T a, T b) {
  T r;
  while (b != 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
template <class T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
int test;
int n;
long long RR;
vector<int> KK[105];
long long HH(long long x) { return x * x * x * x * 3 + 425689 * x - 23156667; }
long long go(int par, int u) {
  long long res = 32131;
  for (int i = 0; i < (((int)(KK[u]).size())); ++i) {
    int v = KK[u][i];
    if (v == par) continue;
    res += HH(go(u, v));
  }
  return res;
}
long long hash_tree(vector<pair<int, int> > V) {
  int d[105];
  memset(d, 0, sizeof(d));
  for (int i = (1); i <= (n); ++i)
    if (((int)(KK[i]).size())) KK[i].clear();
  for (int i = 0; i < (((int)(V).size())); ++i) {
    int u = V[i].first, v = V[i].second;
    KK[u].push_back(v);
    KK[v].push_back(u);
    d[u]++;
    d[v]++;
  }
  int number = 0;
  int que[105], size = 0, que1[105], size1 = 0;
  for (int i = (1); i <= (n); ++i) {
    if (d[i] >= 1) number++;
    if (d[i] == 1) que[size++] = i;
  }
  while (true) {
    if (size <= 2) break;
    size1 = 0;
    for (int t = 0; t < (size); ++t) {
      que1[size1++] = que[t];
    }
    size = 0;
    for (int t = 0; t < (size1); ++t) {
      int u = que1[t];
      for (int j = 0; j < (((int)(KK[u]).size())); ++j) {
        int v = KK[u][j];
        d[v]--;
        if (d[v] == 1) {
          que[size++] = v;
        }
      }
    }
  }
  long long res = 325843;
  vector<long long> Vll;
  for (int i = 0; i < (size); ++i) {
    Vll.push_back(go(0, que[i]));
  }
  sort((Vll).begin(), (Vll).end());
  for (int i = 0; i < (size); ++i) {
    res = res * 1000000007 + Vll[i];
  }
  return res;
}
long long hash_forest(vector<pair<int, int> > V) {
  bool flag[105];
  vector<int> VV[105];
  memset(flag, 0, sizeof(flag));
  for (int i = 0; i < (((int)(V).size())); ++i) {
    int u = V[i].first, v = V[i].second;
    VV[u].push_back(v);
    VV[v].push_back(u);
  }
  vector<long long> Vll;
  for (int i = 1; i <= n; i++)
    if (!flag[i]) {
      flag[i] = 1;
      int que[105], size = 0;
      que[size++] = i;
      vector<pair<int, int> > temp;
      for (int t = 0; t < (size); ++t) {
        int u = que[t];
        for (int j = 0; j < (((int)(VV[u]).size())); ++j) {
          int v = VV[u][j];
          if (!flag[v]) {
            flag[v] = 1;
            que[size++] = v;
            temp.push_back(make_pair(u, v));
          }
        }
      }
      Vll.push_back(hash_tree(temp));
    }
  sort((Vll).begin(), (Vll).end());
  long long res = 132435;
  for (int i = 0; i < ((int)(Vll).size()); i++) res = res * 1000000007 + Vll[i];
  return res;
}
long long hash_alot(vector<vector<pair<int, int> > > V) {
  vector<long long> Vll;
  for (int i = 0; i < ((int)(V).size()); i++) {
    Vll.push_back(hash_forest(V[i]));
  }
  sort((Vll).begin(), (Vll).end());
  long long res = 132435;
  for (int i = 0; i < ((int)(Vll).size()); i++) res = res * 1000000007 + Vll[i];
  return res;
}
bool calcu(vector<pair<int, int> > V) {
  vector<vector<pair<int, int> > > VV;
  for (int i = (1); i <= (n); ++i) {
    vector<pair<int, int> > temp;
    for (int j = 0; j < (((int)(V).size())); ++j) {
      if (V[j].first != i && V[j].second != i) {
        temp.push_back(V[j]);
      }
    }
    VV.push_back(temp);
  }
  long long res = hash_alot(VV);
  return res == RR;
}
void cal(vector<pair<int, int> > V) {
  bool have[105];
  memset(have, 0, sizeof(have));
  for (int i = 0; i < (((int)(V).size())); ++i) {
    int u = V[i].first, v = V[i].second;
    have[u] = 1;
    have[v] = 1;
  }
  for (int i = (1); i <= (n); ++i)
    if (!have[i]) {
      for (int j = (1); j <= (n); ++j)
        if (j != i) {
          vector<pair<int, int> > VV;
          VV = V;
          VV.push_back(make_pair(i, j));
          if (calcu(VV)) {
            cout << "YES\n";
            for (int t = 0; t < (((int)(VV).size())); ++t) {
              cout << VV[t].first << " " << VV[t].second << "\n";
            }
            return;
          }
        }
    }
  cout << "NO\n";
}
void solve() {
  cin >> n >> n;
  vector<vector<pair<int, int> > > V;
  for (int i = 0; i < (n); ++i) {
    int num;
    cin >> num;
    vector<pair<int, int> > temp;
    for (int j = 0; j < (num); ++j) {
      int u, v;
      cin >> u >> v;
      temp.push_back(make_pair(u, v));
    }
    V.push_back(temp);
  }
  RR = hash_alot(V);
  for (int i = 0; i < n; i++) {
    if (((int)(V[i]).size()) == n - 2) {
      cal(V[i]);
      break;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> test;
  for (int itest = 0; itest < (test); ++itest) {
    solve();
  }
  return 0;
}