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) {
			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: import sys
from collections import deque


def bfs(s):
    flag_list[s] = 1
    d_list[s] = 0
    q.append(s)
    while len(q)>0:
        u = q.popleft()
        for v in range(n):
            if m_list[u][v] == 1 and flag_list[v] == 0:
                flag_list[v] = 1
                d_list[v] = d_list[u] + 1
                q.append(v)
        flag_list[u] = 2


if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    m_list = [[0]*n for _ in range(n)]
    d_list = [-1]*n
    flag_list = [0]*n # 0: 未到達, 1: 処理中, 2: 完了
    q = deque([])
    for _ in range(n):
        input_list = list(map(int, input().split()))
        index = input_list[0] - 1
        if input_list[1] > 0:
            for a in input_list[2:]:
                m_list[index][a-1] = 1
    bfs(0)
    for i, d in enumerate(d_list):
        print(i+1, d_list[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, 1)

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

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

    while len(queue) > 0:
        v = queue.pop()
        bfs(v, dist+1)

bfs_init()

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

Python: n = int(input())
a = []
for i in range(n):
  tmp = list(map(int, input().split()))
  a.append(tmp[2:])
ans = [-1 for _ in range(n + 1)]
ans[1] = 0
que = [1]
while len(que) > 0:
  current = que.pop(0)
  if len(a[current - 1]) == 0:
    continue
  for next in a[current - 1]:
    if ans[next] == -1:
      que.append(next)
      ans[next] = ans[current] + 1
for i in range(1, n + 1):
  print(i, ans[i])

Python: N= int(input())
E = [input().split()[2:] for _ in [0]*N]
L,Q = [0] + [-1]*N, [0]
def func(ide):
    for i in E[ide]:
        i = int(i) - 1
        if L[i] < 0 :L[i] = L[ide] +1 ;Q.append(i) 
        else:return

while Q:top = Q.pop();func(top)

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

Python: #coding: UTF-8
from collections import deque
n = int(input())
link = [[] for i in range(n+1)]
for i in range(n):
  r = list(map(int,input().split()))
  u = r.pop(0)
  k = r.pop(0)
  link[u] = r

searched=set()
queue = deque()
d = [-1 for i in range(n+1)]

v = 1
d[v] = 0
queue.append(v)
searched.add(v)
while queue:
  v = queue.popleft()
  for w in link[v]:
    if w not in searched:
      d[w] = d[v] + 1
      queue.append(w)
      searched.add(w)

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

Python: n = int(input())

graphs = []

for _ in range(n):
    graphs.append(list(map(int, input().split()))[2:])


def bfs(graphs, seen_points, score, scores, queue):
    while len(queue) > 0:
        start_point = queue.pop(0)
        if seen_points[start_point - 1] == 2:
            continue
        else:
            next_points = [
                point for point in graphs[start_point - 1] if seen_points[point - 1] == 0]
            if len(next_points) >= 1:
                score += 1
                for point in next_points:
                    queue.append(point)
                    if seen_points[point - 1] == 0:
                        seen_points[point - 1] = 1
                        scores[point - 1] = scores[start_point - 1] + 1
                seen_points[start_point - 1] = 2


seen_points = [0 for _ in range(n)]
scores = [-1 for _ in range(n)]
scores[0] = 0
queue = [1]
bfs(graphs, seen_points, 0, scores, queue)

for index, score in enumerate(scores):
    print(index + 1, score)

Python: import sys
input = sys.stdin.readline

#入力と違って０オリジンとなっているので注意
n = int(input())
li = [[0] * n for _ in range(n)] #隣接行列、０オリジン li[i][j]:iからjへの有向グラフがある
for i in range(n):
    x, y, *v = [int(x)-1 for x in input().split()]
    for j in v:
        li[i][j] = 1 #有向グラフがあるところは１、ないところは０となる

from collections import deque
Q = deque([0]) #初期条件
finish = [0] #訪問済みの頂点をしまう
len_ = [-1]*n #頂点jの頂点０からの距離、できなかったらー１と返す
len_[0] = 0 #初期条件
while Q: #Qがからでない限り以下の操作を繰り返す
    i = Q.popleft()
    for j in range(n):
        if li[i][j] == 1: #iからjへの道が存在する場合
            if not j in finish: #まだjが探索済みじゃなかったら以下の操作を行う
                finish.append(j)
                Q.append(j)
                len_[j] = len_[i] + 1
        else:
            continue
for i in range(n):
    print(str(i+1) + ' ' + str(len_[i]))

Python: n = int(input())
graph = {}
d = [-1] * (n+1)
for i in range(n):
    t = list(map(int, input().split()))
    v = t[0]
    k = t[1]
    graph[v] = [t[i+2] for i in range(k)]

from queue import Queue

def bfs(s):
    d[s] = 0
    q=Queue()
    q.put(s)
    while not q.empty():
        v=q.get()
        for child in graph[v]:
            if d[child] != -1: continue
            d[child] = d[v] + 1
            q.put(child)
bfs(1)
for i in range(1, n+1):print(i,d[i])

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