Go: package main

/*
グラフの表現 隣接行列による表現
*/

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

func main() {
	scanner := makeScanner(8192)
	n := eGetInt(scanner)
	g := make([][]int, n+1)
	for i := 1; i < n+1; i++ {
		g[i] = make([]int, n+1)
		ints := eGetInts(scanner)
		num := ints[0]
		for j := 0; j < ints[1]; j++ {
			g[num][ints[j+2]] = 1
		}
	}
	dist := make([]int, n+1)
	for i := 0; i < len(dist); i++ {
		dist[i] = -1
	}
	q := []int{}

	// 訪問する
	q = append(q, 1)
	dist[1] = 0

	// キューが空でない限り
	for len(q) > 0 {
		// 先頭を取り出す
		top := 0
		top, q = q[0], q[1:]
		// 隣接マスを入れる.
		for i := 1; i < n+1; i++ {
			// 辺がある
			if g[top][i] == 1 {
				if dist[i] == -1 {
					// 訪問済みでなければ
					q = append(q, i)
					dist[i] = dist[top] + 1
				}
			}
		}
	}
	for i := 1; i < n+1; i++ {
		fmt.Println(i, dist[i])
	}
}

////////////////////////////////////////////////////////////////////////////////
// ライブラリ
////////////////////////////////////////////////////////////////////////////////
func makeScanner(maxByte int) *bufio.Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]uint8, 0, 8192), maxByte)
	return scanner
}
func makeWordScanner() *bufio.Scanner {
	scanner := makeScanner(8192)
	scanner.Split(bufio.ScanWords)
	return scanner
}
func eGetLine(r *bufio.Scanner) string {
	if r.Scan() {
		return r.Text()
	}
	err := r.Err()
	if err != nil {
		log.Fatal(err)
	}
	// EOF
	return ""
}
func eGetInt(r *bufio.Scanner) int {
	line := eGetLine(r)
	return eAtoi(line)
}
func eGetInt64(r *bufio.Scanner) int64 {
	line := eGetLine(r)
	return eAtoInt64(line)
}
func eGetFields(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Fields(line)
}
func eGetInts(r *bufio.Scanner) []int {
	fields := eGetFields(r)
	ints := make([]int, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoi(fields[i])
	}
	return ints
}
func eGetInt64s(r *bufio.Scanner) []int64 {
	fields := eGetFields(r)
	ints := make([]int64, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoInt64(fields[i])
	}
	return ints
}
func eGetChars(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Split(line, "")
}
func eAtoi(s string) int {
	n, err := strconv.Atoi(s)
	if err != nil {
		log.Fatal(err)
	}
	return n
}
func eAtoInt64(s string) int64 {
	n, err := strconv.ParseInt(s, 10, 64)
	if err != nil {
		log.Fatal(err)
	}
	return n
}

Python: from collections import deque


def matrix(n):
    for _ in range(n):
        adj = list(map(int, input().split()))
        i = adj[0]
        v = adj[2:]
        for j in v:
            mat[i - 1][j - 1] = 1


def bfs(v):
    d[v] = 1
    dist[v] = 0
    dq.append(v)
    while dq:
        v = dq.popleft()
        for n, i in enumerate(mat[v]):
            if i == 1 and not d[n]:
                d[n] = 1
                dist[n] = dist[v] + 1
                dq.append(n)

n = int(input())
mat = [[0] * n for _ in range(n)]
d, dist = [0] * n, [-1] * n
dq = deque()
matrix(n)
bfs(0)
for i, v in enumerate(dist):
    print(i + 1, v)

Python: #AC

from collections import deque

n=int(input())
G=[[]]
for i in range(n):
    G.append(list(map(int,input().split()))[2:])

#bfs(木でないかも)
L=[-1]*(n+1)
q=deque()

L[1]=0
q.append(1)
while q:
    now=q.popleft()
    L.append(now)
    for next in G[now]:
        #探索済み
        if L[next]>=0:
            continue
        #探索予定(なくて良い)
        #if next in q:
        #    continue
        q.append(next)
        L[next]=L[now]+1

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

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

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_adj_list = v_detail[2:]
        # assert len(v_adj_list) == int(v_detail[1])
        for each in v_adj_list:
            init_adj_matrix[int(v_detail[0]) - 1][int(each) - 1] = 1
    return init_adj_matrix


def graph_bfs(v_init):
    vertices_status_list[v_init] = VISITED_IN_QUEUE
    vertices_distance_list[v_init] = 0
    vertices_visit_queue.appendleft(v_init)

    while vertices_visit_queue:
        current_vertex = vertices_visit_queue.popleft()
        for v in range(1, vertices_num + 1):
            if adj_matrix[current_vertex - 1][v - 1] and vertices_status_list[v] is UNVISITED:
                vertices_status_list[v] = VISITED_IN_QUEUE
                vertices_distance_list[v] = vertices_distance_list[current_vertex] + 1
                vertices_visit_queue.appendleft(v)
        vertices_status_list[current_vertex] = POPPED_OUT
    return vertices_distance_list


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

    # config length = (vertex_num + 1)
    vertices_visit_queue = deque()
    vertices_status_list = [UNVISITED] * vertices_num
    vertices_status_list.insert(0, -1)
    vertices_distance_list = [0] * (vertices_num + 1)

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

Python: N = int(input())
edge = [[] for _ in range(N)]

for _ in range(N):
    l = list(map(int, input().split()))
    for j in range(l[1]):
        edge[l[0]-1].append(l[2+j]-1)


now_list = [0]
next_list = []
dist = 0
dists = [-1] * N
while len(now_list) > 0:
    for _ in range(len(now_list)):
        v = now_list.pop()
        if dists[v] == -1:
            dists[v] = dist
        else:
            continue
        for nv in edge[v]:
            next_list.append(nv)
    now_list = next_list
    next_list = []
    dist += 1

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

Python: from collections import deque
import sys

INFTY=sys.maxsize
WHITE=0
GRAY=1
BLACK=2

color=[]
d=[]
Q=deque([])
n=0
L=[]

def readinput():
    global n
    global L

    n=int(input())
    for i in range(n+1):
        L.append([])

    for i in range(n):
        inp=list(map(int,input().split()))
        L[inp[0]]=inp[2:]


def bfs(s):
    global color
    global d
    global Q

    for i in range(n+1):
        color=[WHITE]*(n+1)
        d=[-1]*(n+1)

    color[s]=GRAY
    d[s]=0
    Q.append(s)

    while(len(Q)>0):
        u = Q.popleft()
        for l in L[u]:
            if(color[l]==WHITE):
                color[l]=GRAY
                d[l]=d[u]+1
                Q.append(l)
        color[u]=BLACK

if __name__=='__main__':
    readinput()
    bfs(1)
    for i in range(1,n+1):
        print('{} {}'.format(i, d[i]))

Python: import numpy as np
N= int(input())
frag, T, L, Q = np.zeros(N),np.zeros(N),np.zeros(N),[0]
# frag, T, L,Q = [0]*N, [0]*N, [0]*N, [0]
a = 100
frag[0] = 1
def func(ide):
#     print("frag = {}".format(frag))
    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
            


E = [input().split()[2:] for _ in range(N)]

while Q:
    top = Q[0]
    func(top)
    del Q[0]
for i in range(N):print(i + 1 ,int(L[i]))

Python: N = int(input())
G = [None for i in range(N)]
for i in range(N):
    u, k, *vs = map(int, input().split())
    G[u-1] = [e-1 for e in vs]


from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

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