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())
d = [-1]*(n+1)
adjacent_list = [[] for _ in range(n+1)]
for _ in range(n):
    edge = list(map(int,input().split()))
    if len(edge) >= 3:
        adjacent_list[edge[0]].extend(edge[2:])

from collections import deque

que = deque()
que.append(1)
d[1] = 0
while len(que) != 0:
    v = que.popleft()
    for nv in adjacent_list[v]:
        if d[nv] == -1:
            d[nv] = d[v] + 1
        else:
            continue
        que.append(nv)

for i,dist in enumerate(d):
    if i == 0:
        continue
    print(i,dist)

Python: from collections import deque
n = int(input())
G = []
for _ in range(n):
    tmp = list(map(int, input().split()))
    u = tmp.pop(0)
    k = tmp.pop(0)
    t = []
    for i in range(k):
        a = tmp.pop(0)
        t.append(a-1)
    G.append(t)
    
dist = [-1]*n
dist[0] = 0
que = deque()
que.append(0)

while que:
    v = que.popleft()
    for nv in G[v]:
        if dist[nv] != -1:
            continue
        dist[nv] = dist[v] + 1
        que.append(nv)
    
for i in range(n):
    print(i+1, dist[i])

Python: def get_depth(graph,tmp_depth,vertex_list,depth_list):
    new_vertex_list=[]
    for vertex in vertex_list:
        for j in range(len(depth_list)):
            if(graph[vertex][j]!=0 and depth_list[j]==-1):
                depth_list[j]=tmp_depth + 1
                new_vertex_list.append(j)
    if(len(new_vertex_list)!=0):
        get_depth(graph,tmp_depth+1,new_vertex_list,depth_list)


#グラフの作成
n=int(input())
graph=[[0]*n for loop in range(n)]
for loop in range(n):
    tmp_ope=list(map(int,input().split()))
    for j in range(tmp_ope[1]):
        graph[tmp_ope[0]-1][tmp_ope[j+2]-1]=1


depth_list=[-1]*n
depth_list[0]=0
vertex_list=[0]
get_depth(graph,0,vertex_list,depth_list)

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

Python: import collections
n = int(input())
adj_list = []

for _ in range(n):
    adj = list(map(int, input().split(" ")))
    adj_list.append([c - 1 for c in adj[2:]])

distances = [-1 for _ in range(n)]
queue = collections.deque()
queue.append(0)
distances[0] = 0

while queue:
    p = queue.popleft()

    for next_p in adj_list[p]:
        if distances[next_p] == -1:
            distances[next_p] = distances[p] + 1
            queue.append(next_p)

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

Python: def breathSerch(P,N):
    n=len(P)-1
    m=1
    QQ=[N[1]]
    while(QQ != []):
        R=[]
        for Q in QQ:
            for i in range(1,n+1):
                if Q[i]==1 and P[i]==-1:
                    P[i]=m
                    R.append(N[i])
        QQ = R
        m=m+1
    
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
breathSerch(P,A)
for i in range(1,n+1):
    print(i,P[i])

Python: n = int(input())
G = [[] for _ in range(n)]
for _ in range(n):
    u, k, *v = [int(i) for i in input().split()]
    G[u - 1] = v
NIL = 100
Q = [[1, 0]]
F = []
D = [NIL for _ in range(n)]
while Q != []:
    u, d = Q.pop(0)
    if d < D[u-1]:
        D[u-1] = d
    if u not in F:
        F.append(u)
    for v in G[u-1]:
        if v not in F:
            Q.append([v, d+1])

for ni in range(1, n):
    Q = [[ni+1, 0]]
    F = []
    while Q != []:
        u, d = Q.pop(0)
        if u == 1 and d < D[ni]:
            D[ni] = d
        if u not in F:
            F.append(u)
        for v in G[u-1]:
            if v not in F:
                Q.append([v, d+1])

for ni in range(n):
    if D[ni] == NIL:
        print(ni+1, -1)
    else:
        print(ni+1, D[ni])

Python: from collections import deque


def breadth_first_search(adj_matrix, n):
    distance = [0] + [-1] * (n - 1)
    searching = deque([0])
    while len(searching) > 0:
        start = searching.popleft()
        for end in range(n):
            if adj_matrix[start][end] and distance[end] == -1:
                searching.append(end)
                distance[end] = distance[start] + 1
    return distance


def main():
    n = int(input())
    adj = [[False for _ in range(n)] for _ in range(n)]
    for _ in range(n):
        ukv = input().split()
        id = int(ukv[0])
        dim = int(ukv[1])
        if dim > 0:
            nodes = map(int, ukv[2:])
            for node in nodes:
                adj[id - 1][node - 1] = True
    distance = breadth_first_search(adj, n)
    for i in range(n):
        print("{} {}".format(i + 1, distance[i]))


if __name__ == "__main__":
    main()

Python: from sys import stdin
from collections import deque
n = int(input())
d = [-1] * (n + 1)
G = [0] + [list(map(int, input().split()[2:])) for _ in range(n)]
d[1] = 0
dq = deque([1])
while len(dq) != 0:
    v = dq.popleft()
    for c in G[v]:
        if d[c] == -1 :
            d[c] = d[v] + 1
            dq.append(c)
for i, x in enumerate(d[1:], start=1):
    print(i, x)

Python: #!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
4
1 2 2 4
2 1 4
3 0
4 1 3

output:
1 0
2 1
3 2
4 1
"""

import sys
from collections import deque

UNVISITED, VISITED_IN_QUEUE, POPPED_OUT = 0, 1, 2


def generate_adj_matrix(v_info):
    for v_detail in v_info:
        v_index, adj_num, *adj_list = map(int, v_detail)
        # assert len(adj_list) == adj_num
        init_adj_table[v_index].extend(adj_list)
    return init_adj_table


def graph_bfs(v_init):
    status[v_init] = VISITED_IN_QUEUE
    distance[v_init] = 0
    queue.appendleft(v_init)

    while queue:
        current = queue.popleft()
        for v in adj_table[current]:
            if status[v] is UNVISITED:
                status[v] = VISITED_IN_QUEUE
                distance[v] = distance[current] + 1
                queue.append(v)
        status[current] = POPPED_OUT
    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    vertices_info = list(map(lambda x: x.split(), _input[1:]))
    init_adj_table = [[] for _ in range(vertices_num + 1)]
    # assert len(vertex_info) == vertex_num

    # config length = (vertex_num + 1)
    queue = deque()
    status = [UNVISITED] * (vertices_num + 1)
    distance = [-1] * (vertices_num + 1)

    adj_table = generate_adj_matrix(vertices_info)
    ans = graph_bfs(1)
    for j in range(vertices_num):
        print(j + 1, ans[j + 1])