Go: package main

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

const MAX = 1000
const NIL = -1

type Node struct {
	id    int
	depth int
}

type Queue struct {
	head      int
	tail      int
	container [MAX]Node
}

func (q *Queue) inQueue(x Node) {
	q.container[q.tail] = x
	q.tail = (q.tail + 1) % MAX
}

func (q *Queue) deQueue() Node {
	x := q.container[q.head]
	q.head = (q.head + 1) % MAX
	return x
}

func (q *Queue) isEmpty() bool {
	return q.head == q.tail
}

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()
	route := make([][]int, n)
	for i := range route {
		u, k := scanInt(), scanInt()
		u--
		route[u] = make([]int, k)
		for j := range route[u] {
			num := scanInt()
			num--
			route[i][j] = num
		}
	}

	d := make([]int, n)
	for i := range d {
		d[i] = NIL
	}

	start := Node{0, 0}
	que := Queue{}
	que.inQueue(start)
	for !que.isEmpty() {
		node := que.deQueue()
		if d[node.id] != NIL {
			continue
		}
		d[node.id] = node.depth

		for _, nextId := range route[node.id] {
			next := Node{id: nextId, depth: node.depth + 1}
			que.inQueue(next)
		}
	}

	for i, depth := range d {
		fmt.Println(i+1, depth)
	}
}

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

"""
input:
4
1 2 2 4
2 1 4
3 0
4 1 3

output:
1 0
2 1
3 2
4 1
"""

import sys
from collections import deque

UNVISITED, VISITED_IN_QUEUE, POPPED_OUT = 0, 1, 2


def graph_bfs(v_init):
    queue = deque()
    status[v_init] = VISITED_IN_QUEUE
    distance[v_init] = 0
    queue.appendleft(v_init)

    while queue:
        current = queue.popleft()
        for adj in adj_table[current]:
            if status[adj] is UNVISITED:
                status[adj] = VISITED_IN_QUEUE
                distance[adj] = distance[current] + 1
                queue.append(adj)
        status[current] = POPPED_OUT
    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num = int(_input[0])
    vertices = list(map(lambda x: x.split(), _input[1:]))
    # assert len(vertex_info) == vertex_num

    status = [UNVISITED] * (v_num + 1)
    distance = [-1] * (v_num + 1)

    adj_table = tuple([] for _ in range(v_num + 1))
    for v_info in vertices:
        v_index, adj_num, *adj_list = map(int, v_info)
        # assert len(adj_list) == adj_num
        adj_table[v_index].extend(adj_list)

    graph_bfs(v_init=1)
    for index, v in enumerate(distance[1:], 1):
        print(index, v)

Python: #!/usr/bin/env python3
import sys
sys.setrecursionlimit(15000)
n = int(sys.stdin.readline())

ret = []
inp = sys.stdin.readlines()
G = [None]*(n+1)
depths = [-1]*(n+1)

for i in range(1,n+1):
  v = list(map(int,inp[i-1].split()))
  G[v[0]] = list(map(int,v[2:]))
#print(G)

nodes = [1]
depth = 0
while nodes:
  new = []
  for i in nodes:
    if depths[i] == -1:
      depths[i] = depth
      new += G[i]
    #print(i,nodes,depth,depths)
  depth += 1
  nodes = new

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

Python: # -*- coding: utf-8 -*-

import sys
from collections import deque

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

N=INT()
nodes=[[] for i in range(N)]
for i in range(N):
    l=LIST()
    u=l[0]
    l=l[2:]
    for v in l:
        nodes[u-1].append(v-1)
    nodes[u-1].sort()

que=deque()
que.append((0, 0))
costs=[-1]*N
while len(que):
    cost,node=que.popleft()
    if costs[node]==-1:
        costs[node]=cost
        for v in nodes[node]:
            que.append((cost+1, v))

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

Python: N = int(input())
E = [[] for _ in range(N+1)]
for _ in range(N):
	tmp = list(map(int, input().split()))
	if tmp[1] == 0:
		continue
	E[tmp[0]] = tmp[2:]

cnt = [0 for _ in range(N+1)]
q = [1]

while q:
	cp = q.pop(0)
	for np in E[cp]:
		if cnt[np] != 0:
			continue
		
		cnt[np] = cnt[cp] + 1
		q.append(np)

for ind, cost in enumerate(cnt):
	if ind == 0:
		continue
	if ind == 1:
		print(ind, 0)
	else:
		if cost == 0:
			print(ind, -1)
		else:
			print(ind, cost)

Python: #coding: utf-8
inf = 100000000
n = int(input())

List = [0] + [list(map(int,input().split())) for i in range(n)]
color = [0] + ["white" for  i in range(n)]
d = [inf for i in range(n+1)]

s = 1
Q = [s]
d[s] = 0
while Q != []:
    q = Q.pop()
    if color[q] == "white":
        k = List[q][1]
        if k != 0:
            Q += List[q][2:2+k]
            for i in List[q][2:2+k]:
                d[i] = min(d[q] + 1, d[i])
    
    color[q] = "black"


for i, dis in enumerate(d[1:], 1):
    print(i, dis)

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