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: import abc


class AdjacentGraph:
    """Implementation adjacency-list Graph.
    Beware ids are between 1 and size.
    """
    def __init__(self, size):
        self.size = size
        self._nodes = [[0] * (size+1) for _ in range(size+1)]

    def set_adj_node(self, id_, adj_id):
        self._nodes[id_][adj_id] = 1

    def __iter__(self):
        self._id = 0
        return self

    def __next__(self):
        if self._id < self.size:
            self._id += 1
            return (self._id, self._nodes[self._id][1:])

        raise StopIteration()

    def dfs(self, handler=None):
        def find_first():
            try:
                return visited.index(0) + 1
            except ValueError:
                return None

        visited = [0] * self.size
        first = 1
        while first is not None:
            stack = [(first, 0, 0)]
            while len(stack) > 0:
                i, depth, j = stack.pop()
                if j == 0:
                    if handler:
                        handler.visit(i, depth)
                    visited[i-1] = 1
                    yield i
                try:
                    j = self._nodes[i].index(1, j+1)
                    stack.append((i, depth, j))
                    if visited[j-1] == 0:
                        stack.append((j, depth+1, 0))
                except ValueError:
                    if handler:
                        handler.leave(i)
            first = find_first()

    def bfs(self, handler=None):
        def find_first():
            try:
                return visited.index(0) + 1
            except ValueError:
                return None

        visited = [0] * self.size
        first = 1
        while first is not None:
            queue = [(first, 0)]
            while len(queue) > 0:
                (i, depth), *queue = queue
                if visited[i-1] == 0:
                    if handler:
                        handler.visit(i, depth)
                    visited[i-1] = 1
                    yield i
                try:
                    j = 0
                    while j < self.size:
                        j = self._nodes[i].index(1, j+1)
                        if visited[j-1] == 0:
                            queue.append((j, depth+1))
                except ValueError:
                    if handler:
                        handler.leave(i)
            first = find_first()


class EventHandler(abc.ABC):
    @abc.abstractmethod
    def visit(self, i, depth):
        pass

    @abc.abstractmethod
    def leave(self, i):
        pass


class Logger(EventHandler):
    def __init__(self, n):
        self.log = [(0, 0)] * n
        self.step = 0

    def visit(self, i, depth):
        self.step += 1
        self.log[i-1] = (self.step, depth, 0)

    def leave(self, i):
        self.step += 1
        self.log[i-1] = (self.log[i-1][0], self.log[i-1][1], self.step)

    def by_node(self):
        i = 1
        for discover, depth, finish in self.log:
            yield (i, discover, depth, finish)
            i += 1

def run():
    n = int(input())
    g = AdjacentGraph(n)
    log = Logger(n)

    for i in range(n):
        id_, c, *links = [int(x) for x in input().split()]
        for n in links:
            g.set_adj_node(id_, n)

    for i in g.bfs(log):
        pass

    reachable = None
    for node in log.by_node():
        id_, find, dep, exit = node
        if id_ > 1 and dep == 0:
            reachable = find - 1

        if reachable is not None and find > reachable:
            dep = -1

        print("{} {}".format(id_, dep))


if __name__ == '__main__':
    run()

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
        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())
g = [None] * n
visited = [0] * n
dist = [-1] * n
queue = deque()

while n:
    l = list(map(int, input().split()))
    connected = [i - 1 for i in l[2:]]
    g[l[0] - 1] = [i - 1 for i in l[2:]]
    n -= 1

queue.append((0, 0))
visited[0] = 1

while queue:
    print(queue)
    i, d = queue.popleft()
    dist[i] = d
    for c in g[i]:
        if not visited[c]:
            visited[c] = 1
            queue.append((c, d + 1))

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

Python: n = int(input())

A = [[] for i in range(n)]

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

f_inf = float("inf")
B = [[f_inf for i in range(2)] for j in range(n)]
B[0][1] = 0

for i in range(n):
  B[i][0] = i+1

def dbs(a):
  global order
  l = len(A[a-1])-2
  if l:
    for i in range(l):
      depth = B[a-1][1]+1
      b = A[a-1][i+2]
      if not b in order or depth < B[b-1][1]:
        B[b-1][1] = depth
        order.append(b)
        dbs(b)

order = [1]
dbs(1)

for i in range(n):
  if B[i][1] == f_inf:
    B[i][1] = -1
  print(" ".join(map(str, B[i])))

Python: # 28
# ALDS_11_C - 幅優先探索

from collections import deque

n = int(input())
u_l = []
k_l = []
v_l = []

for i in range(n):
    _v_l = []
    for j, _ in enumerate(input().split()):
        if j == 0:
            u_l.append(int(_))
        elif j == 1:
            k_l.append(int(_))
        else:
            _v_l.append(int(_))
    v_l.append(_v_l)
        
d_l = [-1]*n
d_l[0] = 0
s_dq = deque([1])
while len(s_dq) > 0:
    _s = s_dq.popleft()
    _s -= 1
    for i in range(k_l[_s]):
        _v = v_l[_s][i]
        if d_l[_v-1] == -1:
            s_dq.append(_v)
            d_l[_v-1] = d_l[_s] + 1

for _id, _d in zip(range(1,n+1), d_l):
    print(_id, _d)

Python: from collections import deque
def bfs(g,v):
    q=deque([v]) ; vis=[0]*n
    vis[v]=1 ; stg[v]=0
    while q:
        v=q[0]
        for p in g[v]:
            if vis[p]==0: 
                q.append(p)
                vis[p]=1
                stg[p]=stg[v]+1
        q.popleft()
n=int(input())
g=[[] for i in range(n)]
for _ in range(n):
    a=[int(i)-1 for i in input().split()]
    for i in a[2:]: g[a[0]].append(i)
stg=[-1]*n
bfs(g,0)
for i in range(n):
    print(i+1,stg[i])