Go: package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	nodes := make([]Node, n)

	for i := 0; i < n; i++ {
		nodes[i].list = make([]int, 0)
		nodes[i].d = -1
	}

	for i := 0; i < n; i++ {
		u := getNextInt(scanner)
		k := getNextInt(scanner)
		u--
		for ii := 0; ii < k; ii++ {
			v := getNextInt(scanner)
			v--
			nodes[u].list = append(nodes[u].list, v)
		}
	}

	queue := make([]int, n)
	queue[0] = 0
	nodes[0].d = 0
	d := 0
	i, j := 0, 1
	for i < j {
		d++
		prev := j
		for i < prev {
			for k, l := 0, len(nodes[queue[i]].list); k < l && i < n; k++ {
				if nodes[nodes[queue[i]].list[k]].d != -1 {
					continue
				}
				nodes[nodes[queue[i]].list[k]].d = d
				queue[j] = nodes[queue[i]].list[k]
				j++
			}
			i++
		}
	}

	for i := 0; i < n; i++ {
		fmt.Fprintln(writer, fmt.Sprintf("%d %d", i+1, nodes[i].d))
	}

	writer.Flush()
}

// Node ...
type Node struct {
	list []int
	d    int
}

Python: n = int(input())

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

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

def bfs(u, d):
    pd = distance[u]
    if pd == -1 or d < pd:
        distance[u] = d
    for v in adj[u]:
        bfs(v, d + 1)


bfs(1, 0)

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

Python: import queue
def s():
 N=int(input())
 M=[input().split()[2:]for _ in[0]*N]
 q=queue.Queue();q.put(0)
 d=[-1]*N;d[0]=0
 while not q.empty():
  u=q.get()
  for v in M[u]:
   v=int(v)-1
   if d[v]<0:d[v]=d[u]+1;q.put(v)
 for i in range(N):print(i+1,d[i])
if'__main__'==__name__:s()

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