Go: package main

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

const MAX = 1000
const NIL = -1

type Node struct {
	id    int
	depth int
}

type Queue struct {
	head      int
	tail      int
	container [MAX]Node
}

func (q *Queue) inQueue(x Node) {
	q.container[q.tail] = x
	q.tail = (q.tail + 1) % MAX
}

func (q *Queue) deQueue() Node {
	x := q.container[q.head]
	q.head = (q.head + 1) % MAX
	return x
}

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

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()
	route := make([][]int, n)
	for i := range route {
		u, k := scanInt(), scanInt()
		u--
		route[u] = make([]int, k)
		for j := range route[u] {
			num := scanInt()
			num--
			route[i][j] = num
		}
	}

	d := make([]int, n)
	for i := range d {
		d[i] = NIL
	}

	start := Node{0, 0}
	que := Queue{}
	que.inQueue(start)
	for !que.isEmpty() {
		node := que.deQueue()
		if d[node.id] != NIL {
			continue
		}
		d[node.id] = node.depth

		for _, nextId := range route[node.id] {
			next := Node{id: nextId, depth: node.depth + 1}
			que.inQueue(next)
		}
	}

	for i, depth := range d {
		fmt.Println(i+1, depth)
	}
}

Python: def MAIN():
    n = int(input())
    li = [[] for _ in range(n + 1)]
    ans = [[i, -1] for i in range(n + 1)]
    ans[1][1] = 0
    for _ in range(n):
        u, k, *v = map(int, input().split())
        li[u] = v
    dp = [1]
    while dp:
        u = dp.pop()
        for v in li[u]:
            if ans[v][1] == -1:
                ans[v][1] = ans[u][1] + 1
                dp.append(v)
    for d in ans[1:]:
        print(*d)
MAIN()

Python: import sys


def bfs(matrix):
    distances = [-1 for _ in range(len(matrix))]
    queue = [0]
    distances[0] = 0

    while 0 < len(queue):
        node_id = queue.pop(0)  # Dequeue
        distance = distances[node_id]
        for index, candidate in enumerate(matrix[node_id]):
            if candidate == 1 and distances[index] == -1:
                # ???????????¢????¨?????????????????????? node
                queue.append(index)
                distances[index] = distance + 1

    return distances

if __name__ == "__main__":
    # ??????????????????
    lines = [
        "4",
        "1 2 2 4",
        "2 1 4",
        "3 0",
        "4 1 3",
    ]
    # lines = sys.stdin.readlines()
    dimension = int(lines[0])
    matrix = [[0 for _ in range(dimension)] for _ in range(dimension)]

    # Set edge info
    for index, line in enumerate(lines[1:]):
        for edge in [int(x) for x in line.strip().split(" ")[2:]]:
            matrix[index][edge - 1] = 1

    distances = bfs(matrix)
    for index, distance in enumerate(distances):
        print("%d %d" % (index + 1, distance))

Python: T = [0]

def curshort(N,k,m,P,n):
    for i in range(1,n+1):
        if P[i]==-1 and N[k][i]==1:
            P[i] = m+1 
            curshort(N,i,m+1,P,n)

n = int(input())
A = [[0 for j in range(n+1)] for i in range(n+1)]


for i in range(n):
    vec = input().split()
    u = int(vec[0])
    k = int(vec[1])
    nodes = vec[2:]
    for i in range(int(k)):
        v = int(nodes[i])
        A[u][v] = 1

P=[-1 for i in range(n+1)]

P[1] = 0
curshort(A,1,0,P,n)
for i in range(1,n+1):
    print(i,P[i])

Python: # https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/11/ALDS1_11_C

from collections import deque

n = int(input())
graph = {}
res = [-1 for i in range(n + 1)]

for i in range(1, n + 1):
    data = input().split()
    graph[i] = [int(i) for i in data[2:]]

visited = set()
q = deque()
q.append((1, 0))  # node,distance
visited.add(1)

while q:
    node, dis = q.popleft()
    res[node] = dis
    for _next in graph[node]:
        if _next not in visited:
            visited.add(_next)
            q.append((_next, dis + 1))

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

Python: n = int(input())
G = [[] for i in range(n)] #G(i): 頂点iと隣接する頂点のlist
for i in range(n):
    a = [int(i) for i in input().split()]
    G[a[0]-1] = [i-1 for i in a[2:]]

d = [-1] * n
todo = [0]
d[0] = 0

while(todo != []):
    v = todo.pop(0)
    for i in G[v]:
        if d[i] == -1:
            d[i] = d[v]+1
            todo.append(i)

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

Python: n = int(raw_input()) 

G = [0 for i in range(n)] 
a = [[0 for i in range(n)] for j in range(n)]
dis = [99999 for i in range(n)]

def bfs_visit(s):
    for k in range(n):
      if a[s][k] == 1:
        if dis[k] > dis[s] + 1:
          dis[k] = dis[s] + 1
          bfs_visit(k)

for i in range(n):
    G = map(int, raw_input().split())
    for j in range(G[1]):
        a[G[0]-1][G[2+j]-1] = 1
 
dis[0] = 0
for s in range(n):
    bfs_visit(s)
for s in range(n):
    if dis[s] == 99999:
       dis[s] = -1
for s in range(n):
    print (s+1, d[s])

Python: # -*- coding:utf-8 -*-

def solve():
    import sys
    import heapq

    N = int(sys.stdin.readline())
    graph = []
    for _ in range(N):
        _in = list(map(int, sys.stdin.readline().split()))
        if len(_in) == 2:
            graph.append([])
            continue
        u, k, Vs = _in[0], _in[1], _in[2:]
        As = []
        for v in Vs:
            As.append(v-1)
        graph.append(As)

    dist = [float("inf") for _ in range(N)]
    dist[0] = 0
    que = []
    heapq.heappush(que, (0, 0))  # (頂点番号, 最短距離の候補)
    while que:
        u, d = heapq.heappop(que)
        if dist[u] < d: continue

        for v in graph[u]:
            if dist[v] > dist[u]+1:
                dist[v] = dist[u]+1
                heapq.heappush(que, (v, dist[v]))

    for i in range(N):
        d = -1 if dist[i]==float("inf") else dist[i]
        print(i+1, d)


if __name__ == "__main__":
    solve()

Python: from collections import deque

n = int(input())
graph = []

for _ in range(n):
    u = list(map(int, input().split()))

    if u[1] == 0:
        graph.append([])
    else:
        graph.append(list(map(lambda x: x - 1, u[2: u[1] + 2])))

dist = [-1] * n


def bfs(x):
    q = deque([])
    dist[x] = 0
    q.append(x)

    while q:
        x = q.popleft()

        for nx in graph[x]:
            if dist[nx] != -1:
                continue
            else:
                dist[nx] = dist[x] + 1
                q.append(nx)


bfs(0)

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

Python: import sys
from collections import deque


def bfs(s):
    flag_list[s] = 1
    d_list[s] = 0
    q.append(s)
    while len(q)>0:
        u = q.popleft()
        for v in range(n):
            if m_list[u][v] == 1 and flag_list[v] == 0:
                flag_list[v] = 1
                d_list[v] = d_list[u] + 1
                q.append(v)
        flag_list[u] = 2


if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    m_list = [[0]*n for _ in range(n)]
    d_list = [-1]*n
    flag_list = [0]*n # 0: 未到達, 1: 処理中, 2: 完了
    q = deque([])
    for _ in range(n):
        input_list = list(map(int, input().split()))
        index = input_list[0] - 1
        if input_list[1] > 0:
            for a in input_list[2:]:
                m_list[index][a-1] = 1
    bfs(0)
    for i, d in enumerate(d_list):
        print(i+1, d_list[i])