Write a program which reads an directed graph $G = (V, E)$, and finds the shortest distance from vertex $1$ to each vertex (the number of edges in the shortest path). Vertices are identified by IDs $1, 2, ... n$.

Constraints

* $1 \leq n \leq 100$

Input

In the first line, an integer $n$ denoting the number of vertices, is given. In the next $n$ lines, adjacent lists of vertex $u$ are given in the following format:

$u$ $k$ $v_1$ $v_2$ ... $v_k$

$u$ is ID of the vertex and $k$ denotes its degree.$v_i$ are IDs of vertices adjacent to $u$.

Output

For each vertex $u$, print $id$ and $d$ in a line. $id$ is ID of vertex $u$ and $d$ is the distance from vertex $1$ to vertex $u$. If there are no path from vertex $1$ to vertex $u$, print -1 as the shortest distance. Print in order of IDs.

Example

Input

4
1 2 2 4
2 1 4
3 0
4 1 3


Output

1 0
2 1
3 2
4 1
import java.util.Scanner;
import java.util.Arrays;
import java.util.Queue;
import java.util.ArrayDeque;



class Main {

    static class aaa {
        public int id;
        public int dis;
    }

    static int n;

    static int[][] graph;

    static int[] d,fin;
 
    static void bfs(int start){
        aaa a,b,c;
        c = new aaa();
        Queue<aaa> queue = new ArrayDeque<aaa>();
        c.id = start;c.dis = 0;
        queue.add(c);

        while(true){
            a = new aaa();
            a = queue.poll();
            //System.out.println(a.id + "  " + fin[a.id]);

            if(a == null)
                break;

            if(fin[a.id] == 1)
                continue;

            d[a.id] = a.dis;

            for(int i = 0;i < graph[a.id].length;i++){
                b = new aaa();
                b.id = graph[a.id][i];b.dis = a.dis + 1;
                if(fin[b.id] == 0){
                    queue.add(b);
                }
            }
            fin[a.id] = 1;
        }
    }

    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt();

        graph = new int[n][];
        d = new int[n];
        fin = new int[n];
        for(int i = 0;i < n;i++){
            fin[i] = 0;
            d[i] = -1;
        }

        for(int i = 0;i < n;i++){
            int u = input.nextInt();
            int k = input.nextInt();
            graph[u - 1] = new int[k];
            for(int j = 0;j < k;j++){
                graph[u - 1][j] = input.nextInt() - 1;
            }
            Arrays.sort(graph[u - 1]);
        }

        bfs(0);

        for(int i = 0;i < n;i++){
            System.out.println((i + 1) + " " + d[i]);
        }
    }
}