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

N = int(input())
nodes = []
G ={}
is_visited = {}
q = deque()

for _ in range(N):
    lst = list(map(int, input().split()))
    idx = lst[0]
    nodes.append(idx)
    is_visited[idx] = False
    degree = lst[1]
    if degree > 0:
        G[idx] = lst[2:]
    else:
        G[idx] = []

INF = 10**12
costs = [INF]*N
# bfs
# 初期queue
que = deque()  # 必要なものはnodeidと原点からの距離
que.append(1)
costs[0] = 0
while que:
    node_id = que.popleft()  # 先入れ先出し
    cost = costs[node_id-1]
    for next_id in G[node_id]:
        if (costs[next_id-1] == INF):
            que.append(next_id)
            costs[next_id-1] = cost + 1
        
for i in range(N):
    if costs[i] != INF:
        print(i+1, costs[i])
    else:
        print(i+1, -1)

Python: from collections import deque


def bfs(start):
    Q = deque()
    Q.append(start)
    dist[start] = 0

    while Q:
        v = Q.popleft()

        for nv in G[v]:
            if dist[nv] != -1:
                continue

            # print(Q)
            dist[nv] = dist[v] + 1
            Q.append(nv)


N = int(input())

G = [[]] + [list(map(int, input().split())) for _ in range(N)]
for a in range(1, N + 1):
    b = G[a][2:]
    G[a] = b

# print(G)
dist = [-1 for _ in range(N + 1)]

start = 1
bfs(start)
# print(dist[1:])
for i in range(1, N + 1):
    print(i, dist[i])

Python: from queue import Queue

n = int(input())
A = [[0 for i in range(n)] for j in range(n)]
d = [-1 for i in range(n)]

for i in range(n):
    u, k, *v = list(map(int, input().split()))
    for j in v:
        A[int(u)-1][int(j)-1] = 1

q = Queue()
q.put(0)
d[0] = 0

while not q.empty():
    u = q.get()
    # print('visited:', u)
    for v in range(n):
        # print(u, v)
        if A[u][v] == 1 and d[v] == -1:
            q.put(v)
            d[v] = d[u] + 1

# print('-========')
for i in range(n):
    print(i, d[i])

Python: import sys
input = sys.stdin.readline
from collections import deque

def main():
	n = int(input().strip())
	v = [[] for _ in range(n)]
	for i in range(n):
		v[i] = list(map(int, input().strip().split()))
	l = [-1] * (n+1)
	q = deque()
	q.append((1, 0))
	while len(q) != 0:
		id, d = q.popleft()
		# print("id", id)
		if l[id] != -1:
			# print("b")
			continue
		l[id] = d
		# l[id] = min(d, l[id])
		# print(id, d)
		for i in range(v[id-1][1]):
			q.append((v[id-1][2+i], d+1))
			# if id == 8:
				# print("##", id, v[id-1][2+i])
				# print(repr(q))
	for i in range(1, n+1):
		print(i, l[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)]
def bfs():
    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)
bfs()

Python: from collections import deque

N = int(input())
graph = [[] for _ in range(N)]
for i in range(N):
  X = list(map(int, input().split()))
  for j in range(2, len(X)):
    graph[i].append(X[j]-1)
    
dist = [-1] * N
dist[0] = 0

q = deque([])
q.append(0)

while q:
  x = q.popleft()
  for next_x in graph[x]:
    if(dist[next_x] > -1):
      continue
    dist[next_x] = dist[x] + 1
    q.append(next_x)
    
for i in range(N):
  print(i+1, dist[i])

Python: from collections import deque

def bfs(maze, visited, x):
    queue = deque([x])
    visited[x] = 1
    ans_list[x] = 0
    while queue:
      #queueには訪れた地点が入っている。そこから、移動できるか考え、queueから消す。
        y = queue.popleft()#queueに入っていたものを消す。
        r = maze[y - 1][2:]
        for i in r:
            if visited[i] == 0:
              if ans_list[i] >= 10 ** 10:
                ans_list[i] = ans_list[y] + 1
                queue.append(i)
    return 0
              

                
if __name__ == "__main__":
  N = int(input())
  A = [0] * N
  for i in range(N):
    A[i] = list(map(int, input().split()))
  visited = [0] * (N + 1)
  ans_list = [float("inf")] * (N + 1)
  bfs(A, visited, 1)
  #print(bfs(A, visited, 1))
  for i in range(1, N + 1):
    if ans_list[i] >= 10 ** 10:
      print(i, -1)
    else:
      print(i, ans_list[i])

Python: from collections import deque
n = int(input())
G = []
for _ in range(n):
    u, k, *v = map(int, input().split())
    u -= 1
    G.append(v)
q = deque()
seen = [False] * n
dist = [-1] * n

def main():
    q.append(0)
    seen[0] = True
    dist[0] = 0
    while len(q) > 0:
        now_v = q.popleft()
        for new_v in G[now_v]:
            new_v -= 1
            if seen[new_v] is True:
                continue
            seen[new_v] = True
            q.append(new_v)
#             print(now_v, new_v)
            dist[new_v] = dist[now_v] + 1
    
    for i in range(n):
        print(i+1, dist[i])

if __name__ == '__main__':
    main()

Python: from collections import deque
n = int(input())
adj = [ [] for _ in range(n+1) ]
for _ in range(n):
  lst = list(map(int,input().split()))
  if lst[1] > 0:
    adj[lst[0]] = lst[2:]

q = deque([1])
dist = [-1] * (n+1)
dist[1] = 0

q = deque([1])
while q:
  node = q.popleft()

  for nei in adj[node]:
    if dist[nei] != -1: continue
    dist[nei] = dist[node] + 1
    q.append(nei)

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