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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.Set;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.TreeSet;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.BitSet;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author I and Bee
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        int n;
        BitSet[] input;
        BitSet[] gr;
        int[] cntAdj;
        BidirectionalGraph graph;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
//        int l = 30, r = 50;


            n = in.readInt();
            input = new BitSet[n];
            long sumSz = 0;
            for (int i = 0; i < n; i++) {
                input[i] = new BitSet(n);
                int sz = in.readInt();
                sumSz += sz;

//            if (n == 50 && l <= i && i < r) out.print(sz);
                for (int j = 0; j < sz; j++) {
                    int val = in.readInt();
                    input[i].set(val - 1);
//                if (n == 50 && l <= i && i < r) out.print("", val);
                }
//            if (n == 50 && l <= i && i < r)  out.printLine();
            }
//        if (n == 50) return;

            if (sumSz == n * n) {
                for (int i = 1; i < n; i++) {
                    out.printLine("1", i + 1);
                }
                return;
            }

            gr = new BitSet[n];
            for (int i = 0; i < n; i++) {
                gr[i] = new BitSet(n);
            }

            Set<IntPair> set;
            set = new TreeSet<>();
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    BitSet gri = (BitSet) input[i].clone();
                    gri.and(input[j]);
                    if (gri.cardinality() == 2) {
                        int a = gri.nextSetBit(0);
                        int b = gri.nextSetBit(a + 1);
                        IntPair pair = new IntPair(Math.min(a, b), Math.max(a, b));
                        set.add(pair);
                        gr[pair.first].set(pair.second);
                        gr[pair.second].set(pair.first);
                    }
                }
            }

            if (set.size() == 1) {
                boolean[] isLeft = new boolean[n];
                IntPair p = set.iterator().next();
                for (BitSet bs : input) {
                    if (bs.cardinality() != n) {
                        for (int i = bs.nextSetBit(0); i != -1; i = bs.nextSetBit(i + 1)) {
                            isLeft[i] = true;
                        }
                        break;
                    }
                }

                out.printLine(p.first + 1, p.second + 1);
                for (int i = 0; i < n; i++) {
                    if (i == p.first) continue;
                    if (i == p.second) continue;
                    if (isLeft[i])
                        out.printLine(p.first + 1, i + 1);
                    else
                        out.printLine(p.second + 1, i + 1);
                }

                return;
            }

            graph = new BidirectionalGraph(n);
            cntAdj = new int[n];
            for (IntPair pair : set) {
                ++cntAdj[pair.first];
                ++cntAdj[pair.second];

                out.printLine(pair.first + 1, pair.second + 1);
                graph.addSimpleEdge(pair.first, pair.second);
            }

//        dfs(set.iterator().next().first, -1);

            for (int list = 0; list < n; list++) {
                if (cntAdj[list] != 0) continue;

                BitSet best = null;
                for (BitSet bitSet : input) {
                    if (bitSet.get(list) && (best == null || best.cardinality() > bitSet.cardinality()))
                        best = bitSet;
                }
//            if (list == 5)
//                for (BitSet bitSet : input) {
//                    if (bitSet.get(list))
//                        System.err.println(bitSet);
//                }


                int cntInV = 0;
                for (int i = best.nextSetBit(0); i != -1; i = best.nextSetBit(i + 1)) {
                    if (cntAdj[i] == 0) continue;
                    ++cntInV;
                }

                int res = -1;
                if (cntInV == 2) {
                    int a = -1;
                    while (cntAdj[a = best.nextSetBit(a + 1)] == 0) ;

                    int b = a;
                    while (cntAdj[b = best.nextSetBit(b + 1)] == 0) ;

                    if (cntAdj[a] == 1 && cntAdj[b] == 1) throw new AssertionError();

                    if (cntAdj[a] == 1) res = a;
                    else if (cntAdj[b] == 1) res = b;
                    else throw new AssertionError();
                } else {
                    int[] cnt = new int[n];
                    for (int i = best.nextSetBit(0); i != -1; i = best.nextSetBit(i + 1)) {
                        if (cntAdj[i] == 0) continue;
                        for (int j = best.nextSetBit(i + 1); j != -1; j = best.nextSetBit(j + 1)) {
                            if (cntAdj[j] == 0) continue;
                            if (gr[i].get(j)) {
                                ++cnt[i];
                                ++cnt[j];
                            }
                        }
                    }
                    for (int i = 0; i < n; i++) {
                        if (2 <= cnt[i]) {
                            if (res == -1)
                                res = i;
                            else
                                throw new MyException();
                        }
                    }
                }

                if (res == -1) throw new MyException();
                out.printLine(list + 1, res + 1);
            }


        }

    }

    static class MyException extends RuntimeException {
        public MyException() {
//        Fail.TLE();
//        Fail.MLE();
        }

    }

    static class Graph {
        protected int vertexCount;
        protected int edgeCount;
        private int[] firstOutbound;
        private int[] firstInbound;
        private Edge[] edges;
        private int[] nextInbound;
        private int[] nextOutbound;
        private int[] from;
        private int[] to;
        private long[] weight;
        public long[] capacity;
        private int[] reverseEdge;
        private int[] flags;

        public Graph(int vertexCount) {
            this(vertexCount, vertexCount);
        }

        public Graph(int vertexCount, int edgeCapacity) {
            this.vertexCount = vertexCount;
            firstOutbound = new int[vertexCount];
            Arrays.fill(firstOutbound, -1);

            from = new int[edgeCapacity];
            to = new int[edgeCapacity];
            nextOutbound = new int[edgeCapacity];
            flags = new int[edgeCapacity];
        }

        public int addEdge(int fromID, int toID, long weight, long capacity, int reverseEdge) {
            ensureEdgeCapacity(edgeCount + 1);
            if (firstOutbound[fromID] != -1)
                nextOutbound[edgeCount] = firstOutbound[fromID];
            else
                nextOutbound[edgeCount] = -1;
            firstOutbound[fromID] = edgeCount;
            if (firstInbound != null) {
                if (firstInbound[toID] != -1)
                    nextInbound[edgeCount] = firstInbound[toID];
                else
                    nextInbound[edgeCount] = -1;
                firstInbound[toID] = edgeCount;
            }
            this.from[edgeCount] = fromID;
            this.to[edgeCount] = toID;
            if (capacity != 0) {
                if (this.capacity == null)
                    this.capacity = new long[from.length];
                this.capacity[edgeCount] = capacity;
            }
            if (weight != 0) {
                if (this.weight == null)
                    this.weight = new long[from.length];
                this.weight[edgeCount] = weight;
            }
            if (reverseEdge != -1) {
                if (this.reverseEdge == null) {
                    this.reverseEdge = new int[from.length];
                    Arrays.fill(this.reverseEdge, 0, edgeCount, -1);
                }
                this.reverseEdge[edgeCount] = reverseEdge;
            }
            if (edges != null)
                edges[edgeCount] = createEdge(edgeCount);
            return edgeCount++;
        }

        protected final Graph.GraphEdge createEdge(int id) {
            return new Graph.GraphEdge(id);
        }

        public final int addFlowWeightedEdge(int from, int to, long weight, long capacity) {
            if (capacity == 0) {
                return addEdge(from, to, weight, 0, -1);
            } else {
                int lastEdgeCount = edgeCount;
                addEdge(to, from, -weight, 0, lastEdgeCount + entriesPerEdge());
                return addEdge(from, to, weight, capacity, lastEdgeCount);
            }
        }

        protected int entriesPerEdge() {
            return 1;
        }

        public final int addWeightedEdge(int from, int to, long weight) {
            return addFlowWeightedEdge(from, to, weight, 0);
        }

        public final int addSimpleEdge(int from, int to) {
            return addWeightedEdge(from, to, 0);
        }

        protected final int edgeCapacity() {
            return from.length;
        }

        protected void ensureEdgeCapacity(int size) {
            if (from.length < size) {
                int newSize = Math.max(size, 2 * from.length);
                if (edges != null)
                    edges = resize(edges, newSize);
                from = resize(from, newSize);
                to = resize(to, newSize);
                nextOutbound = resize(nextOutbound, newSize);
                if (nextInbound != null)
                    nextInbound = resize(nextInbound, newSize);
                if (weight != null)
                    weight = resize(weight, newSize);
                if (capacity != null)
                    capacity = resize(capacity, newSize);
                if (reverseEdge != null)
                    reverseEdge = resize(reverseEdge, newSize);
                flags = resize(flags, newSize);
            }
        }

        protected final int[] resize(int[] array, int size) {
            int[] newArray = new int[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        private long[] resize(long[] array, int size) {
            long[] newArray = new long[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        private Edge[] resize(Edge[] array, int size) {
            Edge[] newArray = new Edge[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        protected class GraphEdge implements Edge {
            protected int id;

            protected GraphEdge(int id) {
                this.id = id;
            }

        }

    }

    static class IntPair implements Comparable<IntPair> {
        public final int first;
        public final int second;

        public IntPair(int first, int second) {
            this.first = first;
            this.second = second;
        }


        public String toString() {
            return "(" + first + "," + second + ")";
        }


        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            IntPair intPair = (IntPair) o;

            return first == intPair.first && second == intPair.second;

        }


        public int hashCode() {
            int result = first;
            result = 31 * result + second;
            return result;
        }

        public int compareTo(IntPair o) {
            if (first < o.first)
                return -1;
            if (first > o.first)
                return 1;
            if (second < o.second)
                return -1;
            if (second > o.second)
                return 1;
            return 0;
        }

    }

    static class BidirectionalGraph extends Graph {
        public int[] transposedEdge;

        public BidirectionalGraph(int vertexCount) {
            this(vertexCount, vertexCount);
        }

        public BidirectionalGraph(int vertexCount, int edgeCapacity) {
            super(vertexCount, 2 * edgeCapacity);
            transposedEdge = new int[2 * edgeCapacity];
        }


        public int addEdge(int fromID, int toID, long weight, long capacity, int reverseEdge) {
            int lastEdgeCount = edgeCount;
            super.addEdge(fromID, toID, weight, capacity, reverseEdge);
            super.addEdge(toID, fromID, weight, capacity, reverseEdge == -1 ? -1 : reverseEdge + 1);
            this.transposedEdge[lastEdgeCount] = lastEdgeCount + 1;
            this.transposedEdge[lastEdgeCount + 1] = lastEdgeCount;
            return lastEdgeCount;
        }


        protected int entriesPerEdge() {
            return 2;
        }


        protected void ensureEdgeCapacity(int size) {
            if (size > edgeCapacity()) {
                super.ensureEdgeCapacity(size);
                transposedEdge = resize(transposedEdge, edgeCapacity());
            }
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0)
                    writer.print(' ');
                writer.print(objects[i]);
            }
        }

        public void printLine(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

    }

    static interface Edge {
    }
}