Go: package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

func stringifyArray(arr []int) string {
	return strings.TrimRight(fmt.Sprintf("%+v", arr)[1:], "]")
}

var infty = 1000000000

type nodeKey int

type DirectedGraphNode struct {
	key       nodeKey
	adjacents []*DirectedGraphNode
	visited   bool
	d         int
	parent    *DirectedGraphNode
}

type DirectedGraph struct {
	nodes []DirectedGraphNode
}

func (g *DirectedGraph) setAdjacency(l, r nodeKey) {
	g.nodes[l].adjacents = append(g.nodes[l].adjacents, &g.nodes[r])
}

func newDirectedGraph(nNodes int) *DirectedGraph {
	graph := DirectedGraph{}
	graph.nodes = make([]DirectedGraphNode, nNodes)
	for iNodes := 0; iNodes < nNodes; iNodes++ {
		graph.nodes[iNodes].key = nodeKey(iNodes)

		graph.nodes[iNodes].visited = false
		graph.nodes[iNodes].d = infty
		graph.nodes[iNodes].parent = nil
	}
	return &graph
}

type QueueEntry struct {
	node *DirectedGraphNode
	next *QueueEntry
}

type Queue struct {
	head, tail *QueueEntry
}

func (q *Queue) enqueue(node *DirectedGraphNode) {
	entry := QueueEntry{}
	entry.node = node

	if q.tail == nil {
		q.head = &entry
		q.tail = &entry
		return
	}

	q.tail.next = &entry
	q.tail = q.tail.next
}

func (q *Queue) dequeue() *QueueEntry {
	if q.head == nil {
		return nil
	}
	poped := q.head
	q.head = q.head.next
	if q.head == nil {
		q.tail = nil
	}
	return poped
}

func (q *Queue) isEmpty() bool {
	return q.head == nil
}

func fillDistancesByBreadthFirstSearch(g *DirectedGraph, startNode *DirectedGraphNode) {
	startNode.visited = true
	startNode.d = 0

	queue := Queue{}
	queue.enqueue(startNode)
	for !queue.isEmpty() {
		u := queue.dequeue().node
		for _, adjacent := range u.adjacents {
			if !adjacent.visited {
				adjacent.visited = true
				adjacent.d = u.d + 1
				adjacent.parent = u
				queue.enqueue(adjacent)
			}
		}
		u.visited = true
	}
}

func main() {
	scanner.Split(bufio.ScanWords)

	nNodes := nextInt()
	g := newDirectedGraph(nNodes + 1)

	for iNode := 0; iNode < nNodes; iNode++ {
		nodeKeyLeft := nodeKey(nextInt())
		nAdj := nextInt()
		for iAdj := 0; iAdj < nAdj; iAdj++ {
			nodeKeyRight := nodeKey(nextInt())
			g.setAdjacency(nodeKeyLeft, nodeKeyRight)
		}
	}

	// fmt.Println(g)
	fillDistancesByBreadthFirstSearch(g, &g.nodes[1])
	// fmt.Println(g)

	for iNode := 1; iNode <= nNodes; iNode++ {
		node := g.nodes[iNode]
		distance := node.d
		if distance == infty {
			distance = -1
		}
		fmt.Println(node.key, distance)
	}
}

Python: from collections import deque


def bfs(g, source):
    n = len(g)
    d = [float('inf') for _ in range(n)]
    d[0] = 0
    queue = deque()
    queue.append(0)
    while len(queue) > 0:
        cur = queue.popleft()
        for next in g[cur]:
            if d[cur] + 1 < d[next]:
                d[next] = d[cur] + 1
                queue.append(next)
    return d


def main():
    n = int(input())
    g = [[] for _ in range(n)]
    for _ in range(n):
        inp = list(map(int, input().split()))
        m = inp[0] - 1
        k = inp[1]
        for i in range(k):
            g[m].append(inp[i+2] - 1)
    d = bfs(g, 0)
    for i in range(n):
        if d[i] == float('inf'):
            d[i] = -1
        print(i+1, d[i])


if __name__ == '__main__':
    main()

Python: import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from collections import deque,defaultdict,Counter
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N):
        A = list(map(int,input().split()))
        for a in A[2:]:
            a -= 1
            G[i].append(a)
    
    q = deque([0])
    dist = [-1] * N
    dist[0] = 0
    while q:
        v = q.popleft()
        for e in G[v]:
            if dist[e] >= 0:
                continue
            dist[e] = dist[v] + 1
            q.append(e)
    
    ans = [(i + 1,dist[i]) for i in range(N)]
    for t in ans:
        print(*t)
if __name__ == '__main__':
    main()

Python: from collections import deque
n=int(input())
E=[0]*n
for _ in range(n):
    u,k,*V=map(int,input().split())
    E[u-1]=V
d=[-1]*n
d[0]=0
todo=deque([1])
while todo:
    now=todo.popleft()
    for v in E[now-1]:
        if d[v-1]==-1:
            todo.append(v)
            d[v-1]=d[now-1]+1
for i in range(n):
    print(i+1,d[i])

Python: from sys import stdin
from collections import deque

n = int(stdin.readline())
g = [None] * n
for _ in range(n):
    u, _, *cs = [int(s) for s in stdin.readline().split()]
    g[u-1] = [c - 1 for c in cs]
ds = [-1] * n
v = [False] * n
v[0] = True
q = deque([(0, 0)])
while len(q):
    u, d = q.popleft()
    ds[u] = d
    for c in g[u]:
        if not v[c]:
            v[c] = True
            q.append((c, d + 1))
for u, d in enumerate(ds):
    print(u + 1, d)

Python: from collections import deque

N = int(input())                            # 頂点数

conj = [[] for _ in range(N)]
for i in range(N):                          # 各頂点での進める先の候補の集合
    L = list(map(int, input().split()))
    for a in L[2:]:
        conj[i].append(a-1)         # 頂点番号をデクリメント

start = 0

visit = [False]*N                           # 訪れたかどうかをメモ
second_visit = [False]*N                    # 二度目に訪れた事をメモ
next_set = deque()                          # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
next_set.append((start, 0))                 # スタート地点を決める。第二成分は時刻を表す。
visit[start] = True                         # スタート地点は最初から踏んでいる。
res = [-1 for _ in range(N)]
res[0] = 0

while next_set:                             # p = [] になったら止める
    p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
    for q in conj[p]:                       # 頂点 p から進める経路の候補から一つ選ぶ
        if not visit[q]:                    # 訪れた事がない場所のみ進む。壁などの条件がある場合は、ここに " grid[p] != 壁 " 等を追加する
            visit[q] = True                 # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            res[q] = t + 1
            next_set.append((q, t + 1))     # p から q へと移動。時刻を 1 進める


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

Python: from collections import deque
n = int(input())
A = [0]*(n+1)
D = [0]*(n+1)
DP = [0]*(n+1)
d = deque()
for i in range(n):
    A[i+1] = [int(i) for i in input().split()]
d.append(1)
DP[1]=0
while(len(d)>0):
    tmp = d.pop()
    for i in A[tmp][2:]:
        if not DP[i]:
            D[i] = D[tmp]+1
            DP[i] = 1
            d.appendleft(i)
for i in range(1,n+1):
    tmp = "{} {}".format(i,D[i])
    print(tmp)

Python: import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

n = int(input())
dis = [-1] * n
info = [list(map(int, input().split())) for _ in range(n)]

stack = [[0, 0]]
ans = 0
while len(stack) > 0:
    num = stack.pop(0)
    if dis[num[0]] == -1:
        dis[num[0]] = num[1]
    for i in info[num[0]][2:]:
        if dis[i-1] == -1:
            stack.append([i - 1, num[1] + 1])
for i in range(n):
    print(str(i+1) + " " + str(dis[i]))

Python: n=int(input())
ne=[[] for _ in range(n+1)]
for _ in range(n):
    u,k,*v=map(int,input().split())
    ne[u]=v
dis=[-1]*(n+1)
dis[1]=0
q=[1]
while q:
    p=q.pop(0)
    for e in ne[p]:
        if dis[e]==-1:
            dis[e]=dis[p]+1
            q.append(e)
for i in range(1,n+1):
    print(i,dis[i])