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: n = int(input())

m = [[0 for _ in range(n+1)] for _ in range(n+1)]
#mm = [[] for _ in range(n+1)]

for _ in range(n):
	tmp = [int(x) for x in input().split()]
	u,k,l = tmp[0],tmp[1],tmp[2:]
	#mm[u] += tmp[2:]
	for x in l:
		m[u][x] = 1
		
dp = [float('inf') for _ in range(n+1)]
dp[1] = 0
queue = [1]

while queue:
	t = queue.pop(0)
	for i,x in enumerate(m[t]):
		if x == 1:
			if dp[i] > dp[t] + 1:
				dp[i] = dp[t] + 1
				queue.append(i)
			else:
				pass
		else:
			pass
			
for i,x in enumerate(dp):
	if i == 0:
		pass
	else:
		if x == float('inf'):
			print(i, -1)
		else:
			print(i, x)

Python: import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def bfs(adj, nxt, dis, sumi, kyori):
    nnxt = []
    for u in nxt:
        sumi[u] = True
        dis[u] = kyori

    for u in nxt:
        for v in adj[u]:
            if not sumi[v]:
                nnxt.append(v)

    return nnxt, kyori + 1

def solve():
    n = int(input())
    adj = [None] * n
    for i in range(n):
        u, k, *vs = [int(j) - 1 for j in input().split()]
        adj[u] = vs

    # debug(adj, locals())

    sumi = [False] * n
    dis = [-1] * n
    nxt = [0]
    kyori = 0

    while nxt:
        nxt, kyori = bfs(adj, nxt, dis, sumi, kyori)

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

    pass

if __name__ == '__main__':
    solve()

Python: from collections import deque
n = int(input())
edges = [[]] + [list(map(int, input().split())) for _ in range(n)]
inf = 10 ** 4
d = [inf for _ in range(n+1)]

que = deque()
d[1] = 0
que.append(1)
while que:
    cur = que.popleft()
    for to in edges[cur]:
        if d[to] == inf:
            d[to] = d[cur] + 1
            que.append(to)

for i in range(1, n+1):
    if d[i] == inf:
        d[i] = -1
    print(i, d[i])

Python: N= int(input())
E = [input().split()[2:] for _ in range(N)]
Q = [0]
L = [0] + [-1]*N
frag = [1] + [0]*N
def func(ide):
    global Q
    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 None
    

while Q:top = Q[0];func(top);del Q[0]

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

Python: 
def BFS(s = 0, time = 0):
    d[s] = time
    if len(Q) != 0:
        Q.pop(0)
        color[s] = 2
    for j in range(len(d)):
        if A[i][j] == 1 and color[j] == 0:
            Q.append(A[i][j])
            color[j] = 1
    for j in range(Q):
        time = time + 1
        BFS(Q[j], time)

n = int(raw_input())
A = [0] * n
for i in range(n):
    A[i] = [0] * n

for i in range(n):
    value = map(int, raw_input().split())
    u = value[0] - 1
    k = value[1]
    nodes = value[2:]
    for j in range(k):
        v = nodes[j] - 1
        A[u][v] = 1

color = [0] * n
Q = [0]
d = [-1] * n

BFS(0, 0)

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

Python: n = int(input())
adj = [list(map(int, input().split()))[2:] for _ in range(n)]

d = [-1] * n

s = 1
q = []
d[s - 1] = 0
q.append(s)
while len(q):
    u = q.pop()
    v = adj[u - 1]
    for vi in v:
        if d[vi - 1] == -1:
            d[vi - 1] = d[u - 1] + 1         
            q.append(vi)
        elif d[vi - 1] > d[u - 1] + 1:
            d[vi - 1] = d[u - 1] + 1            
            q.append(vi)

for i, di in enumerate(d):
    print(i + 1, di)

Python: from collections import deque

N = int(input())
E = [None] * (N+1)
for _ in range(N):
    u, k, *vs = list(map(int, input().split()))
    E[u] = vs

d = [-1] * (N+1)
d[1] = 0
q = deque([(1, 0)])
while q:
    v, c = q.popleft()
    for u in E[v]:
        if d[u] < 0:
            d[u] = c+1
            q.append((u, c+1))

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

Python: from collections import deque
from enum import Enum, auto

class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

n = int(input())
d = [0 for i in range(n)]
f = [0 for i in range(n)]

colors = [] # 頂点の訪問状態
A = [[0 for j in range(n)] for i in range(n)] # 隣接行列
queue = deque([])

# 隣接行列の初期化
for i in range(n):
    arr = list(map(int, input().split(' ')))
    u, k, v = arr[0], arr[1], arr[2:]
    for j in range(k):
        A[u-1][v[j]-1] = 1

def bfs_init():
    global colors
    colors = [Color.WHITE for i in range(n)]
    d[0] = 0
    bfs(0)

def bfs(u):
    global queue
    colors[u] = Color.GRAY

    for v in range(n):
        if A[u][v] == 1 and colors[v] == Color.WHITE and v not in queue:
            d[v] = d[u] + 1
            queue.append(v)

    while len(queue) > 0:
        v = queue.pop()
        bfs(v)

bfs_init()

for u in range(n):
    if colors[u] == Color.WHITE:
        d[u] = -1

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

Python: import queue
n = int(input())

g = {}
for i in range(n):
    x = list(map(int, input().split()))
    g[x[0]] = [x[2:], 'w', x[0], None]

q = queue.Queue()
node = g[1]
node[-1] = 0
node[1] = 'g'
q.put(node)

while not q.empty():
    node  = q.get()
    d = node[-1] + 1
    for i in node[0]:
        ch = g[i]
        if ch[1] == 'w':
            ch[-1] = d
            ch[1] = 'g'
            q.put(ch)

for i in range(n):
    node = g[i+1]
    if node[-1] == None:
        d = -1
    else:
        d = node[-1]
    print("{} {}".format(i+1, d))

Python: #!/usr/bin/env python3

from collections import deque

n = int(input())

edges = [[] for _ in range(n)]
for _ in range(n):
    line = list(map(int, input().split()))
    u = line[0] - 1
    if len(line) != 2:
        v_list = line[1:]
        for v in v_list:
            edges[u].append(v - 1)
# print(n, edges)

dist = [-1 for _ in range(n)]
que = deque()


def dfs(que, dist):
    while len(que) > 0:
        v = que.popleft()

        for v_adj in edges[v]:
            if dist[v_adj] == -1:
                dist[v_adj] = dist[v] + 1
                que.append(v_adj)


dist[0] = 0
que.appendleft(0)
dfs(que, dist)

for i in range(n):
    print(f"{i + 1} {dist[i]}")