Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Scan()
	num, _ := strconv.Atoi(sc.Text())
	nodes := make(map[int]*node)

	for i := 0; i < num; i++ {
		sc.Scan()
		id, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		nodeNum, _ := strconv.Atoi(sc.Text())
		n := node{id, make([]int, 0), -1}
		for j := 0; j < nodeNum; j++ {
			sc.Scan()
			nid, _ := strconv.Atoi(sc.Text())
			n.nexts = append(n.nexts, nid)
		}
		nodes[id] = &n
	}
	nodes[1].depth = 0

	walk(1, 0, &nodes)
	for i := 1; i < len(nodes)+1; i++ {
		fmt.Printf("%v %v\n", (*nodes[i]).id, (*nodes[i]).depth)
	}
}

var time int
var record [100][100]bool
var q Queue

func walk(nid int, from int, nodes *map[int]*node) {
	q.Enqueue((*nodes)[nid])
	for !q.IsEmpty() {
		n := q.Dequeue().(*node)
		for _, v := range n.nexts {
			n2 := (*nodes)[v]
			if n2.depth != -1 {
				continue
			}
			n2.depth = n.depth + 1
			q.Enqueue((*nodes)[v])
		}
	}
}

type node struct {
	id    int
	nexts []int
	depth int
}

// Queue is Queue
type Queue struct {
	val []interface{}
}

// Enqueue value
func (queue *Queue) Enqueue(val interface{}) {
	queue.val = append(queue.val, val)
}

// Dequeue value
func (queue *Queue) Dequeue() interface{} {
	res := queue.val[0]
	queue.val = queue.val[1:len(queue.val)]
	return res
}

// IsEmpty return true when queue is empty
func (queue *Queue) IsEmpty() bool {
	return len(queue.val) == 0
}

Python: from collections import deque
n = int(input())
G = [[0]*n for _ in range(n)]
for _ in range(n):
    u, k, *V = map(int, input().split())
    if k == 0:
        continue
    else:
        for v in V:
            G[u-1][v-1] = 1



def bfs(u=0):
    Q = deque([])
    color = ['White']*n
    d = [-1]*n

    d[0] = 0
    Q.append(u)
    while Q:
        u = Q.popleft()
        for v in range(n):
            if G[u][v] == 1 and color[v] == 'White':
                if d[v] != -1:
                    continue
                color[v] = 'Gray'
                d[v] = d[u] + 1
                Q.append(v)
        color[u] = 'Black'

    return d

D = bfs()
for i in range(n):
    print('{} {}'.format(i+1, D[i]))

Python: N= int(input())
E = [input().split()[2:] for _ in range(N)]
frag, T, L,Q = [0]*N, [0]*N, [0]*N, [0]
a,frag[0] = 100, 1
def func(ide):
    for i in E[ide]:
        i = int(i) - 1
        if frag[i] != 1:frag[i] = 1;L[i] = L[ide] +1 ;Q.append(i) 
        else:return

while Q:top = Q[0];func(top);del Q[0]
for i in range(N):
    if L[i] == 0:
        L[i] == -1

for i in range(N):print(i + 1 ,int(L[i]))

Python: def BFS(s, r):
    flag[s] = 1
    d[s] = r
    for i in range(1, n+1):
        if G[s][i] == 1 and flag[i] == 0:
            BFS(i, r+1)

n = int(raw_input())
G = [[0 for i in range(n+1)] for j in range(n+1)]
d = [-1 for i in range(n+1)]

for i in range(n):
    v = map(int, raw_input().split())
    for j in range(v[1]):
        G[v[0]][v[2+j]] = 1

flag = [0 for i in range(n+1)]
BFS(1, 0)

for i in range(1, n+1):
    print(str(i) + " " + str(d[i]))

Python: N = int(input())
G = [None for i in range(N)]
for i in range(N):
    u, k, *vs = map(int, input().split())
    G[u-1] = [e-1 for e in vs]


from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

for i in range(N):
    print(i+1, dist[i])

Python: from collections import deque


def BFS(num):
    color=["white" for _ in range(n+1)]
    D=[-1 for _ in range(n+1)]

    color[num]="gray"
    D[num]=0
    queue=deque([num])

    while len(queue)>0:
        u=queue.popleft()
        for i in M[u]:
            if color[i]=="white":
                color[i]="gray"
                D[i]=D[u]+1
                queue.append(i)
        color[u]="black"

    return D


n=int(input())

M=[[] for _ in range(n+1)]
for i in range(n):
    for j in list(map(int,input().split()))[2:]:
        M[i+1].append(j)

D=BFS(1)
for i in range(1,n+1):
    print(i,D[i])

Python: from collections import deque
import sys


def bfs():
    color[0] = "GRAY"
    d[0] = 0
    Q.append(0)
    while len(Q) != 0:
        u = Q.popleft()
        for v in range(n):
            if M[u][v] and color[v] == "WHITE":
                color[v] = "GRAY"
                d[v] = d[u] + 1
                Q.append(v)
        color[u] = "BLACK"


if __name__ == "__main__":
    n = int(sys.stdin.readline())
    M = [[0] * n for i in range(n)]
    color = ["WHITE"] * n
    d = [-1] * n
    Q = deque()
    for inp in sys.stdin.readlines():
        inp = list(map(int, inp.split()))
        for i in inp[2:]:
            M[inp[0]-1][i-1] = 1
    bfs()
    for i in range(n):
        print(i+1, d[i])

Python: n = int(input())
graph = [[0 for i in range(n)] for j in range(n)]
d = [0] * n
f = [0] * n
queue = [0]


for i in range(n):
   a = list(map(int, input().split()))
   for j in range(0, a[1], 1):
       graph[a[0] - 1][a[2 + j] - 1] = 1

while len(queue) != 0:
    i = queue.pop(0)
    for j in range(n):
        if (graph[i][j] == 1) & (f[j] == 0):
            queue.append(j)
            f[j] = 1
            d[j] = d[i] + 1

[print(i+1, d[i] if (i == 0) | (d[i] != 0) else -1) for i in range(n)]

Python: # -*- coding: utf-8 -*-
"""
Created on Sun Jul  8 10:56:33 2018

@author: maezawa
"""
n = int(input())
adj = [[] for _ in range(n)]
d = [-1 for _ in range(n)]
d[0] = 0


for j in range(n):
    ain = list(map(int, input().split()))
    u = ain[0]
    k = ain[1]
    for i in range(k):
        adj[u-1].append(ain[i+2]-1)
    adj[u-1].sort()
    #print(*adj[u-1])

stack = [0]

while stack:
    print(stack)
    current = stack[-1]
    flag = 0
    for k in adj[current]:
        if d[k] < 0:
            d[k] = d[current]+1
            stack.append(k)
            flag = 1
        elif d[k] > d[current]+1:
            d[k] = d[current]+1
    if flag == 0:
        stack.pop()

    #print('current = {}, t = {}'.format(current, t))
    #print('stack', *stack)

for i in range(n):
    print('{} {}'.format(i+1, d[i]))

Python: n = int(input())

G = []
G.append([])
for i in range(n):
    v = list(map(int, input().split()))
    G.append(v[2:])

q = []
q.append(1)

checked = [False] * (n + 1)
checked[1] = True
d = [-1] * (n + 1)
d[1] = 0

while q:
    current = q.pop(0)
    for v in G[current]:
        if not checked[v]:
            q.append(v)
            d[v] = d[current] + 1
            checked[v] = True

for i in range(1, n + 1):
    print(i, d[i])

Python: n = int(input())
G = {i:[] for i in range(1, n+1)}
for _ in range(n):
    ukv = list(map(int, input().split()))
    u = ukv[0]
    k = ukv[1]
    for i in range(2, 2+k):
        G[u].append(ukv[i])
        
stack = [1]
dist = [-1]*(n+1)
dist[1] = 0

while stack:
    target = stack.pop(0)
    for target_i in G[target]:
        if dist[target_i]==-1:
            dist[target_i] = dist[target]+1
            stack.append(target_i)
            
for i, dist_i in enumerate(dist[1:], 1):
    print(i, dist_i)