Go: package main

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

var distance []int

type queue struct {
	q    []int
	head int
	tail int
}

func (q *queue) push(n int) {
	q.q[q.tail] = n
	q.tail++
}

func (q *queue) pop() int {
	q.head++
	return q.q[q.head-1]
}

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

func makeAdjList() [][]int {
	var n int
	fmt.Scanf("%d", &n)

	adj := make([][]int, n)
	for i := 0; i < n; i++ {
		adj[i] = make([]int, n)
	}

	sc := bufio.NewScanner(os.Stdin)
	for i := 0; i < n; i++ {
		sc.Scan()
		nodeInfo := strings.Split(sc.Text(), " ")
		outDegree, _ := strconv.Atoi(nodeInfo[1])

		if outDegree > 0 {
			for k := 0; k < outDegree; k++ {
				j, _ := strconv.Atoi(nodeInfo[k+2])
				j-- // convert 1 based to 0 based
				adj[i][j] = 1
			}
		}
	}

	return adj
}

func bfs(graph [][]int, s int) {
	distance = make([]int, len(graph))

	infty := -1
	for i := 0; i < len(distance); i++ {
		distance[i] = infty
	}
	distance[s] = 0

	q := &queue{make([]int, 1000), 0, 0}
	q.push(s)

	for !q.isEmpty() {
		u := q.pop()
		for i := 0; i < len(graph); i++ {
			if graph[u][i] == 0 {
				continue // u, i間に辺がない場合
			}
			if distance[i] != infty {
				continue // 訪問済みの場合
			}
			// 訪問するnodeの始点からの距離を設定し、訪問キューに入れる
			distance[i] = distance[u] + 1
			q.push(i)
		}
	}

	// print distance
	for i, d := range distance {
		fmt.Printf("%d %d\n", i+1, d)
	}
}

func main() {
	adj := makeAdjList()
	bfs(adj, 0)
}

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])