Go: package main

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

type AdjacentList struct {
	matrix [][]int
}

func NewEmptyAdjacentList(dim int) *AdjacentList {
	matrix := make([][]int, dim)
	for i := 0; i < dim; i++ {
		matrix[i] = make([]int, dim)
	}
	return &AdjacentList{matrix: matrix}
}

func (al *AdjacentList) set(node int, adjacent int) {
	al.matrix[node-1][adjacent-1] = 1
}

func (al *AdjacentList) findAdjacentsFor(node int) []int {
	adjacents := []int{}
	for i, v := range al.matrix[node-1] {
		if v == 1 {
			adjacents = append(adjacents, i+1)
		}
	}
	return adjacents
}

type DistanceList struct {
	list []int
}

func NewDistanceList(dim int) *DistanceList {
	list := make([]int, dim)
	for i := 0; i < dim; i++ {
		list[i] = -1
	}
	return &DistanceList{list: list}
}

func (dl *DistanceList) set(node int, distance int) {
	dl.list[node-1] = distance
}

func (dl *DistanceList) get(node int) int {
	return dl.list[node-1]
}

func (dl *DistanceList) isVisited(node int) bool {
	return dl.list[node-1] >= 0
}

type Position struct {
	node     int
	distance int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	dim, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	al := NewEmptyAdjacentList(dim)

	for i := 1; i <= dim; i++ {
		node, err := nextInt(sc)
		if err != nil {
			panic(err)
		}

		adjacentNum, err := nextInt(sc)
		if err != nil {
			panic(err)
		}
		for j := 0; j < adjacentNum; j++ {
			adjacent, err := nextInt(sc)
			if err != nil {
				panic(err)
			}
			al.set(node, adjacent)
		}
	}

	dl := NewDistanceList(dim)

	bfs(al, dl)

	for i := 1; i <= dim; i++ {
		fmt.Printf("%d %d\n", i, dl.get(i))
	}
}

func bfs(al *AdjacentList, dl *DistanceList) {
	stack := []Position{Position{node: 1, distance: 0}}
	for len(stack) > 0 {
		currentPosition := stack[0]
		stack = stack[1:]
		if !dl.isVisited(currentPosition.node) {
			dl.set(currentPosition.node, currentPosition.distance)
		}
		for _, v := range al.findAdjacentsFor(currentPosition.node) {
			if !dl.isVisited(v) {
				stack = append(stack, Position{node: v, distance: currentPosition.distance + 1})
			}
		}
	}
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

Python: from collections import deque

n = int(input())
li = [list(map(int, input().split())) for _ in range(n)]

graph = [[] for _ in range(n+1)]
for u, k, *v in li:
    for i in v:
        graph[u].append(i)

ans = [-1] * (n+1)

ans[1] = 0
stack = deque([1])
while stack:
    num = stack.popleft()

    for s in graph[num]:
        if ans[s] == -1:
            stack.append(s)
            ans[s] = ans[num] + 1
            
for i, v in enumerate(ans[1:]):
    print(i+1, v)

Python: # -*- coding: utf-8 -*-
from collections import deque


if __name__ == '__main__':

    n = int(input())
    M = [[0 for i in range(n)] for j in range(n)]
    for _ in range(n):
        l = list(map(int, input().split(" ")))
        u = l[0]
        k = l[1]
        if k != 0:
            for v in l[2:]:
                M[u - 1][v - 1] = 1

    color = [0] * n
    d = [-1] * n
    Q = deque()

    def bfs(s):  # breadth-first search
        color[s] = 1
        d[s] = 0
        Q.append(s)

        while len(Q) != 0:
            u = Q.popleft()
            for v in range(n):
                if M[u][v] == 1 and color[v] == 0:
                    color[v] = 1
                    d[v] = d[u] + 1
                    Q.append(v)
            color[u] = 2

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

Python: import sys
input = lambda: sys.stdin.readline().rstrip() 
from collections import deque

def resolve():
    n = int(input())
    ukv = [list(map(int, input().split())) for _ in range(n)]

    dist = [-1]*n
    que = deque()

    que.append(0)
    dist[0] = 0
    while len(que)>0:
        v = que.popleft()
        for i in ukv[v][2:]:
            if dist[i-1]==-1:
                que.append(i-1)
                dist[i-1] = dist[v]+1

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

if __name__ == '__main__':
    resolve()

Python: #!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
from collections import deque

n=int(input())
G=[0]*n
memo=[0]*n
dis=[0]*n
dis[0]=1
que=deque()
que.append((0,1))

for i in range(n):
    inp=tuple(map(int,input().split()))
    G[inp[0]-1]=inp[2:]

while que:
    vertex,d=que.popleft()
    for v in G[vertex]:
        if not dis[v-1]:
            dis[v-1]=d+1
            que.append((v-1,d+1))
        

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

Python: def MAIN():
    n = int(input())
    li = [[] for _ in range(n + 1)]
    ans = [[i, 0] for i in range(n + 1)]
    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] == 0:
                ans[v][1] = ans[u][1] + 1
                dp.append(v)
    for d in ans[1:]:
        print(*d)
MAIN()

Python: from collections import deque

class Vertex:
    _id = -1
    _children = []
    _depth = -1

    def __init__(self, i, c):
        self._id = i
        self._children = c

    def getId(self):
        return self._id

    def getChildren(self):
        return self._children

    def getDepth(self):
        return self._depth

    def setDepth(self, d):
        self._depth = d

    def print(self):
        print("{} {}".format(self._id, self._depth))


n = int(input())
graph = [0 for i in range(n)]
queue = deque([])

# 頂点登録
for i in range(n):
    u = list(map(int, input().split(' ')))
    adj = []
    if u[1] > 0:
        adj = u[2:u[1]+2]
    graph[u[0]-1] = Vertex(u[0], adj)

# BFS
graph[0].setDepth(0)
queue.append(graph[0])
while queue:
    v = queue.popleft()
    for u_id in v.getChildren():
        u = graph[u_id-1]
        if u.getDepth() == -1:
            u.setDepth(v.getDepth()+1)
            queue.append(u)

# 回答を出力
for v in graph:
    v.print()

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
'''

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

Python: def srch(i, l, Lng, Dst):
    if Lng[i] != -1 and Lng[i] < l:
        return
    Lng[i] = l
    if Dst[i] is not None and len(Dst[i]) > 0:
        for c in Dst[i]:
            srch(c,l+1, Lng, Dst)

def main():
    num = int(input())
    Dst = [None for i in range(num + 1)]
    Lng = [-1] * (num + 1)
    
    for n in range(1, num+1):
        a = list(map(int,input().split()))
        u = a[0]
        if a[1] > 0:
            Dst[u] = a[2:]

    srch(1, 0, Lng, Dst)

    for n in range(1, num+1):
        l = Lng[n]
        if l > num:
            l = -1
        print("{} {}".format(n,l))

if __name__ == '__main__':
    main()