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

icase=0
if icase==0:
    n=int(input())
    u=[0]*n
#    g = [deque([]) for _ in range(n)]
    g = [[] for _ in range(n)]
    for i in range(n):
        ukv=list(map(int,input().split()))
        u[i]=ukv[0]-1
        ki=ukv[1]
        v=ukv[2:]
        for vi in v:
            g[u[i]].append(vi-1)
#            g[vi-1].append(u[i])
elif icase==1:
    n=4
    g = [[] for _ in range(n)]
    g[0]=[1,3]
    g[1]=[0,3]
    g[2]=[3]
    g[3]=[0,1,2]
#ans:0 1 2 1

q=deque([0])

stack=[0]
parent=[-1]*n
parent[0]=0
dist=[-1]*n
dist[0]=0
while q:
    state = q.popleft()
#    print("--- q:",q,"state:",state,"g:",g[state],"p:",parent)
    for v in g[state]:
#        print("  state:",state,"v:",v,"q:",q)
#        if parent[state] == v:
        if parent[v] !=-1:
            continue
        else:
#            print("parent:",parent,"xx:",xx,"stack",stack)
            parent[v]=state
            dist[v]=dist[state]+1
            q.append(v)
#            print(" state:",state,"v:",v,"parent:",parent,"stack",stack,"dist[v]",dist[v])

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

Python: import sys
from collections import deque

inf = 1<<30

def solve():
    n = int(input())
    Adj = [None] * n

    for i in range(n):
        u, k, *line = [int(i) - 1 for i in input().split()]
        Adj[u] = line

    d = bfs(n, Adj)

    for i, di in enumerate(d, start=1):
        if di == inf:
            print(i, -1)
        else:
            print(i, di)

def bfs(n, Adj):
    d = [inf] * n
    d[0] = 0
    nxts = deque([0])

    while nxts:
        u = nxts.popleft()

        for v in Adj[u]:
            if d[v] == inf:
                d[v] = d[u] + 1
                nxts.append(v)

    return d

if __name__ == '__main__':
    solve()

Python: def bfs(adj, s):
    n = len(adj)
    d = [-1 for _ in range(n)]
    c = [0 for _ in range(n)]

    d[s] = 0
    c[s] = 1

    queue = [s]

    while len(queue) > 0:
        u = queue.pop(0)
        for v in adj[u]:
            if c[v] == 0:
                c[v] = 1
                d[v] = d[u] + 1
                queue.append(v)

    return d


n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n):
    s = [int(x) for x in input().split()]
    u = s[0]
    for v in s[2:]:
        adj[u - 1].append(v - 1)

d = bfs(adj, 0)

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

Python: #!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	breadth_first_search
# CreatedDate:  2020-04-14 23:40:14 +0900
# LastModified: 2020-04-15 00:14:09 +0900
#


import os
import sys
from collections import deque

def bfs(matrix,n):
    s=0
    color=[0]*n
    color[s]=1
    Q=deque()
    Q.append(s)
    distance = [-1]*n
    distance[0]=0
    while Q:
        u = Q.popleft()
        for v in matrix[u]:
            if color[v]==0:
#                print("{}->{}".format(u,v))
                distance[v]=distance[u]+1
                color[v]=1
                Q.append(v)
        color[u]=2
    
    return distance

def main():
    n=int(input())
    matrix = [[] for _ in range(n)]
    for i in range(n):
        lined = map(int,input().split())
#        print(lined)
        for j,pon in enumerate(lined):
            if j>=2:
                matrix[i].append(pon-1)
#    print(matrix)
    distance = bfs(matrix,n)
    for i,di in enumerate(distance):
        print("{} {}".format(i+1,di))

if __name__ == "__main__":
    main()

Python: n = int(input())
a = [101] * n
a[0] = 0
for i in range(n):
    t = list(map(int, input().split()))
    del t[1]
    if len(t) >= 2:
        for j in range(1, len(t)):
            a[t[j] - 1] = min(a[t[j] - 1], a[t[0] - 1] + 1)
for i in range(n):
    if a[i] == 101:
        print("{} {}".format(i + 1, -1))
    else:
        print("{} {}".format(i + 1, a[i]))

Python: from collections import deque

n = int(input())
graph = [[] for _ in range(n)]
for i in range(n):
    graph[i] += list(map(lambda x: x - 1, list(map(int, input().split()))[2:]))

visited = [-1] * n
que = deque()
# 頂点0を入れておく
que.append(0)
visited[0] = 0
cnt = 0

while que:
    v = que.popleft()
    for nv in graph[v]:
        if not visited[nv] == -1:
            continue
        visited[nv] = visited[v] + 1
        que.append(nv)

for v, d in enumerate(visited, 1):
    print(v, d)

Python: from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def bfs(graph, initial):
    n = len(graph) - 1
    dist = [-1] * (n + 1)
    q = deque([initial])
    visited = [False] * (n + 1)
    visited[initial] = True
    dist[initial] = 0

    while len(q) != 0:
        edge = q.popleft()
        nxt = graph[edge]

        for i, e in enumerate(nxt):
            if visited[e] is False:
                q.append(e)
                dist[e] = dist[edge] + 1
                visited[e] = True

    return dist


def main():
    N = I()
    graph = [[] for i in range(N+1)]

    for i in range(N):
        a = LI()
        edge = a[0]
        if a[1] == 0:
            continue
        for e in a[2:]:
            graph[edge].append(e)
            # graph[e].append(edge)

    # print(graph)
    ret = bfs(graph, 1)
    for i in range(1, N+1):
        print(i, ret[i])


if __name__ == '__main__':
    main()