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 Queue
class Node:
    def __init__(self,v):
        self.v = v
        self.c = []

def bfs(n):
    d = {n.v:0}
    q = Queue.Queue()
    q.put(n)
    visited = set([n.v])
    while q.qsize() > 0:
        x = q.get()
        for c in x.c:
            if not c.v in visited:
                q.put(c)
                d[c.v] = d[x.v]+1
                visited.add(c.v)
    return d



n = int(raw_input())
nodes = {}
for _ in range(n):
    entry = map(int,raw_input().split(' '))
    nid = entry[0]
    if not nid in nodes: nodes[nid] = Node(nid)
    k = entry[1]
    if k > 0:
        children = entry[2:]
        for c in children:
            if not c in nodes: nodes[c] = Node(c)
            nodes[nid].c.append(nodes[c])

d = bfs(nodes[1])
for nid in nodes:
    if not nid in d:
        d[nid] = -1
for k in d:
    print k,d[k]