Problem: Archaeologists found some information about an ancient land of Treeland. We know for sure that the Treeland consisted of n cities connected by the n - 1 road, such that you can get from each city to any other one along the roads. However, the information about the specific design of roads in Treeland has been lost. The only thing that the archaeologists can use is the preserved information about near cities.

Two cities of Treeland were called near, if it were possible to move from one city to the other one by moving through at most two roads. Also, a city is considered near to itself. During the recent excavations archaeologists found a set of n notes, each of them represents a list of cities, near to some of the n cities of the country. However, unfortunately, none of the found records lets you understand in what order the cities go in the list and for which city in the list the near to it cities were listed. 

Help the archaeologists and restore any variant of the map of Treeland that meets the found information.

Input

The first line contains integer n (2 ≤ n ≤ 1000) — the number of cities in the country. 

Next n lines describe the found lists of near cities. Each list starts from number k (1 ≤ k ≤ n), representing the number of cities in the list followed by k city numbers. All numbers in each list are distinct.

It is guaranteed that the given information determines at least one possible road map.

Output

Print n - 1 pairs of numbers representing the roads of the country. The i-th line must contain two integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi), showing that there is a road between cities ai and bi.

The answer you print must satisfy the description of close cities from the input. You may print the roads of the countries in any order. The cities that are connected by a road may also be printed in any order.

If there are multiple good answers, you may print any of them.

Examples

Input

5
4 3 2 4 1
5 5 3 2 4 1
5 4 2 1 5 3
4 2 1 4 3
3 1 4 5


Output

1 4
1 2
1 3
4 5


Input

6
5 6 1 3 4 2
5 2 1 3 4 6
6 3 6 2 5 4 1
6 6 1 2 5 3 4
3 5 2 4
5 3 1 2 4 6


Output

2 4
1 2
2 3
2 6
4 5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int base = 62;
const int inf = 1e9 + 9;
int n, ans[1001], len[1001], per[1001], adj[1001][1001], num[1001], deep[1001];
bool vis[1001], is[1001];
bool cmp(int id1, int id2) { return len[id1] < len[id2]; }
struct bt {
  long long bit[1000 / base + 5];
  bool operator<(const bt &temp) const {
    for (int i = 0; i <= n / base; i++) {
      if (bit[i] < temp.bit[i]) return true;
      if (bit[i] > temp.bit[i]) return false;
    }
    return false;
  }
};
bt bs[1001];
int pa[1001];
long long mbit[1001 / base + 5];
bool dfs(int id, long long bit[], int parent) {
  int num_yes, num_no, i, j, s, p, q, low, high, mid, choose, sec, ax = -1, ip,
                                                                   thr;
  long long nbit[1000 / base + 5], lf[1001];
  bool ft = false;
  vector<int> ls;
  ls.clear();
  for (i = 0; i < n; i++) {
    if (vis[i]) continue;
    for (j = 0; j <= n / base; j++) {
      long long tu = (bit[j] & bs[i].bit[j]);
      if (tu != bit[j]) break;
    }
    if (j > n / base) {
      if (parent >= 0)
        ip = pa[parent];
      else
        continue;
      for (j = 0; j <= n / base; j++) nbit[j] = (bs[i].bit[j] & bs[ip].bit[j]);
      lf[i] = 0;
      for (j = 0; j <= n / base; j++) {
        while (nbit[j]) {
          lf[i]++;
          nbit[j] = (nbit[j] & (nbit[j] - 1));
        }
      }
      if (ax < lf[i])
        ax = lf[i];
      else if (ax == lf[i]) {
        if (lf[i] >= 3) {
          ft = true;
          break;
        }
      }
    }
  }
  for (i = 0; i < n; i++) {
    if (vis[i]) continue;
    bool zero = true;
    for (j = 0; j <= n / base; j++) {
      long long tu = (bit[j] & bs[i].bit[j]);
      if (bit[j] != 0) zero = false;
      if (tu != bit[j]) break;
    }
    if (j > n / base && !zero) {
      if (parent < 0 || ft || lf[i] == ax) ls.push_back(i);
    }
  }
  if (parent < 0 && ls.size() <= 1) return false;
  if (parent < 0) {
    for (int ii = 0; ii < ls.size(); ii++) {
      i = ls[ii];
      for (j = 0; j <= n / base; j++) {
        if (bs[i].bit[j] != bit[j]) break;
      }
      if (j > n / base) is[i] = true;
    }
  }
  choose = -1;
  sec = -1;
  for (int ii = 0; ii < ls.size(); ii++) {
    i = ls[ii];
    if (parent < 0) {
      if (is[i]) continue;
      num_yes = num_no = 0;
      for (int jj = 0; jj < ls.size(); jj++) {
        j = ls[jj];
        if (is[j] || j == i) continue;
        for (s = 0; s <= n / base; s++) {
          if ((bs[i].bit[s] ^ bit[s]) & (bs[j].bit[s] ^ bit[s])) break;
        }
        if (s > n / base)
          num_yes++;
        else
          num_no++;
        if (num_yes >= 1 || num_no >= 2) break;
      }
      if (num_no >= 2)
        choose = i;
      else if (num_yes == 0 && (choose < 0 || len[choose] > len[i]))
        choose = i;
    }
  }
  if (parent < 0) {
    if (choose < 0) {
      if (ls[0] != id)
        choose = ls[0];
      else
        choose = ls[1];
    }
    vis[choose] = true;
    vis[id] = true;
    pa[id] = choose;
    for (i = 0; i <= n / base; i++) {
      nbit[i] = (bs[choose].bit[i] ^ bit[i]);
      mbit[i] = 0;
    }
    for (int ii = 0; ii < ls.size(); ii++) {
      i = ls[ii];
      if (i == id || i == choose) continue;
      vis[i] = true;
      for (j = 0; j <= n / base; j++) {
        if (mbit[j] & (bs[i].bit[j] ^ bit[j])) return false;
      }
      for (j = 0; j <= n / base; j++) mbit[j] |= (bs[i].bit[j] ^ bit[j]);
    }
    for (i = 0; i <= n / base; i++) {
      if ((mbit[i] & nbit[i]) != nbit[i]) return false;
    }
    for (int ii = 0; ii < ls.size(); ii++) {
      i = ls[ii];
      if (i == id || i == choose) continue;
      pa[i] = choose;
      for (j = 0; j <= n / base; j++)
        nbit[j] = (bs[i].bit[j] ^ bit[j]) & (bs[choose].bit[j] ^ bit[j]);
      dfs(id, nbit, i);
    }
  } else {
    id = pa[parent];
    for (int ii = 0; ii < ls.size(); ii++) vis[ls[ii]] = true;
    for (int ii = 0; ii < ls.size(); ii++) {
      i = ls[ii];
      pa[i] = parent;
      for (j = 0; j <= n / base; j++) {
        nbit[j] = (bs[parent].bit[j] ^ (bs[parent].bit[j] & bs[id].bit[j]));
        nbit[j] = (nbit[j] & bs[i].bit[j]);
      }
      dfs(id, nbit, i);
    }
  }
  return true;
}
void t_dfs(int id) {
  int i, j, s, p, q, ip;
  for (i = 0; i < num[id]; i++) {
    ip = adj[id][i];
    if (ip == pa[id]) continue;
    deep[ip] = deep[id] + 1;
    t_dfs(ip);
  }
}
int main() {
  int i, j, s, p, q, k, id, ip, in, root, id1, id2, cn, ip1, ip2;
  long long bw;
  scanf("%d", &n);
  for (i = 0; i < n; i++) memset(bs[i].bit, 0, sizeof(bs[i].bit));
  in = inf;
  for (i = 0; i < n; i++) {
    scanf("%d", &k);
    len[i] = k;
    for (j = 0; j < k; j++) {
      scanf("%d", &id);
      id--;
      bs[i].bit[id / base] |= ((long long)1 << (long long)(id % base));
    }
  }
  for (i = 0; i < n; i++) per[i] = i;
  sort(per, per + n, cmp);
  int ii;
  for (ii = 0; ii < n; ii++) {
    i = per[ii];
    memset(pa, -1, sizeof(pa));
    memset(vis, false, sizeof(vis));
    memset(is, false, sizeof(is));
    if (dfs(i, bs[i].bit, -1)) break;
  }
  for (i = 0; i < n; i++) num[i] = 0;
  for (i = 0; i < n; i++) {
    if (pa[i] >= 0) {
      adj[i][num[i]++] = pa[i];
      adj[pa[i]][num[pa[i]]++] = i;
    }
  }
  for (root = 0; root < n; root++) {
    if (pa[root] < 0) break;
  }
  memset(ans, -1, sizeof(ans));
  deep[root] = 0;
  t_dfs(root);
  memset(vis, false, sizeof(vis));
  for (i = 0; i < n; i++)
    for (j = i + 1; j < n; j++) {
      id1 = i;
      id2 = j;
      cn = 0;
      while (id1 != id2) {
        if (deep[id1] > deep[id2]) {
          id1 = pa[id1];
          cn++;
        } else {
          id2 = pa[id2];
          cn++;
        }
        if (cn > 4) break;
      }
      if (cn == 4) {
        if (deep[i] > deep[j])
          id1 = pa[pa[i]];
        else
          id1 = pa[pa[j]];
        for (s = 0; s <= n / base; s++) {
          if ((bs[i].bit[s] & bs[j].bit[s])) {
            bw = (bs[i].bit[s] & bs[j].bit[s]);
            break;
          }
        }
        for (p = 0; p < base; p++) {
          if (bw & ((long long)1 << (long long)p)) break;
        }
        id = s * base + p;
        ans[id1] = id;
        vis[id] = true;
      }
    }
  for (i = 0; i < n; i++)
    for (j = i + 1; j < n; j++) {
      id1 = i;
      id2 = j;
      cn = 0;
      while (id1 != id2) {
        if (deep[id1] > deep[id2]) {
          id1 = pa[id1];
          cn++;
        } else {
          id2 = pa[id2];
          cn++;
        }
        if (cn > 3) break;
      }
      if (cn == 3) {
        if (deep[i] > deep[j]) {
          id1 = pa[i];
          id2 = pa[pa[i]];
        } else {
          id1 = pa[j];
          id2 = pa[pa[j]];
        }
        for (s = 0; s <= n / base && (ans[id1] < 0 || ans[id2] < 0); s++) {
          if ((bs[i].bit[s] & bs[j].bit[s])) {
            bw = (bs[i].bit[s] & bs[j].bit[s]);
            for (p = 0; p < base && bw; p++) {
              if (bw & ((long long)1 << (long long)p)) {
                id = s * base + p;
                if (ans[id1] < 0 && !vis[id]) {
                  ans[id1] = id;
                  vis[id] = true;
                }
                if (ans[id2] < 0 && !vis[id]) {
                  ans[id2] = id;
                  vis[id] = true;
                }
                bw ^= ((long long)1 << (long long)p);
              }
            }
          }
        }
      }
    }
  for (i = 0; i < n; i++) {
    if (num[i] >= 2) {
      id1 = adj[i][0];
      id2 = adj[i][1];
      j = 0;
      for (s = 0; s <= n / base; s++) {
        bw = (bs[id1].bit[s] & bs[id2].bit[s]);
        for (p = 0; p < base && bw; p++) {
          if (bw & (1LL << p)) {
            id = s * base + p;
            if (!vis[id]) {
              while (j < num[i] && ans[adj[i][j]] >= 0) j++;
              if (j < num[i]) {
                vis[id] = true;
                ans[adj[i][j]] = id;
              }
            }
            bw ^= (1LL << p);
          }
        }
      }
    }
  }
  for (i = 0; i < n; i++) {
    if (ans[i] < 0) {
      for (j = 0; j < n; j++) {
        if (!vis[j]) {
          ans[i] = j;
          vis[j] = true;
          break;
        }
      }
    }
  }
  for (i = 0; i < n; i++) {
    if (pa[i] >= 0) printf("%d %d\n", ans[i] + 1, ans[pa[i]] + 1);
  }
}