Go: package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
type Queue struct {
	arr []int
}

func (q *Queue) push(v int) {
	q.arr = append(q.arr, v)
}

func (q *Queue) pop() int {
	res := q.arr[0]
	q.arr = q.arr[1:]
	return res
}

func (q *Queue) isEmpty() bool {
	return len(q.arr) == 0
}

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N := sc.nextInt()
	G := make([][]int, N)
	for i := 0; i < N; i++ {
		u, k := sc.nextInt()-1, sc.nextInt()
		for j := 0; j < k; j++ {
			G[u] = append(G[u], sc.nextInt()-1)
		}
	}
	var q Queue
	seen := make([]int, N)
	for i := 0; i < N; i++ {
		seen[i] = -1
	}
	var search func(cur int)
	search = func(cur int) {
		for i := 0; i < len(G[cur]); i++ {
			next := G[cur][i]
			if seen[next] == -1 {
				q.push(next)
				seen[next] = seen[cur] + 1
			}
		}
	}
	q.push(0)
	seen[0] = 0
	for !q.isEmpty() {
		search(q.pop())
	}

	for i := 0; i < N; i++ {
		fmt.Fprintln(wtr, i+1, seen[i])
	}
	wtr.Flush()
}

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()

Python: N= int(input())
E = [input().split()[2:] for _ in range(N)]
Q = [0]
L = [0] + [-1]*N
frag = [1] + [0]*N
def func(ide):
    global Q
    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
    

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())

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

isSearched = [None] + [False] * n

distance = [None] + [-1] * n

import collections

def bfs(u):
    isSearched[u] = True
    distance[u] = 0
    edge = collections.deque()
    edge.append(u)
    while edge:
        c_e = edge.popleft()
        for n_e in adj[c_e]:
            if not isSearched[n_e]:
                isSearched[n_e] = True
                distance[n_e] = distance[c_e] + 1
                edge.append(n_e)


bfs(1)

for i, x in enumerate(distance[1:], start=1):
    print(i, x)

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

import sys


def bfs(matrix):
    distances = [-1 for _ in range(len(matrix))]
    queue = [0]
    distances[0] = 0

    while 0 < len(queue):
        node_id = queue.pop(0)  # Dequeue
        distance = distances[node_id]
        for index, candidate in enumerate(matrix[node_id]):
            if candidate == 1 and distances[index] == -1:
                # ???????????¢????¨?????????????????????? node
                queue.append(index)
                distances[index] = distance + 1

    return distances

if __name__ == "__main__":
    # ??????????????????
    # lines = [
    #     "4",
    #     "1 2 2 4",
    #     "2 1 4",
    #     "3 0",
    #     "4 1 3",
    # ]
    lines = sys.stdin.readlines()
    dimension = int(lines[0])
    matrix = [[0 for _ in range(dimension)] for _ in range(dimension)]

    # Set edge info
    for index, line in enumerate(lines[1:]):
        for edge in [int(x) for x in line.strip().split(" ")[2:]]:
            matrix[index][edge - 1] = 1

    distances = bfs(matrix)
    for index, distance in enumerate(distances):
        print("%d %d" % (index + 1, distance))

Python: from collections import deque
from typing import List
import sys


def bfs(adj_list: List[List[int]]) -> List[int]:
    n = len(adj_list)
    result: List[int] = [sys.maxsize for _ in range(n)]
    result[0] = 0
    queue: deque = deque()
    queue.append(0)

    while len(queue) > 0:
        cur = queue.popleft()
        for vertex in adj_list[cur]:
            if result[cur] + 1 < result[vertex]:
                result[vertex] = result[cur] + 1
                queue.append(vertex)

    return result


if __name__ == "__main__":
    num_vertices = int(input())
    adj_list: List[List[int]] = [[] for _ in range(num_vertices)]

    for _ in range(num_vertices):
        vertex, num_adjs, *adjs = map(lambda x: int(x), input().split())
        for i in range(num_adjs):
            adj_list[vertex - 1].append(adjs[i] - 1)

    result = bfs(adj_list)

    for i in range(num_vertices):
        if sys.maxsize == result[i]:
            result[i] = -1
        print(f"{i + 1} {result[i]}")

Python: #coding:utf-8
                
def BFS(i,A,d,dist):
    dist[i]=d
    for point in A[i]:
        if dist[point-1]==-1 or dist[point-1]>d+1:
            BFS(point-1,A,d+1,dist)

if __name__=="__main__":
    n=int(input())
    A=[]
    for i in range(n):
        A.append(list(map(int,input().split(" ")))[2:])
    dist=[-1]*n
    BFS(0,A,0,dist)

    for i in range(n):
        print("{} {}".format(i+1,dist[i]))

Python: import collections

N = int(input())
G = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    u,k,*varray = map(int,input().split())
    for v in varray:
        G[u-1][v-1] = 1
        
D = [-1 for _ in range(N)]
D[0] = 0
Q = collections.deque()
Q.append(0)
while len(Q) > 0:
    # print("bfs",Q)
    cur = Q.popleft()
    for dst in range(N):
        if G[cur][dst] == 1 and D[dst] == -1:
            D[dst] = D[cur] + 1
            Q.append(dst)
for v in range(N):
    print(v+1, D[v])
            

# 順番を書こう。落ち着け
# まずd=1の時→行列の一行目をみよう
# 1になっている列を探す→そいつらのDは全部2に変える
# プラスしてそいつらのしもべたちを3にする
#

Python: import queue

N = int(input())
L = [list(map(int,input().split())) for _ in range(N)]
V = [(i+1) for i in range(N)]
E = []
for i in range(N):
    for j in range(len(L[i])-2):
        E.append((i+1,L[i][j+2]))

class Graph:
    def __init__(self,v,e):
        self.v = v
        self.e = e
        self.v_visited = [False for _ in range(N)]
    def visited(self,v):
        self.v_visited[v-1] = True

q = queue.Queue()
g = Graph(V,E)
TS = [-1 for _ in range(N)]

def bfs(u):
    q.put(u)
    g.visited(u)
    TS[u-1] = 0
    while not q.empty():
        u = q.get()
        for v in g.v:
            if (u,v) in g.e and g.v_visited[v-1] == False:
                q.put(v)
                g.visited(v)
                TS[v-1] = TS[u-1]+1
bfs(1)

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