Go: package main

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

func main() {
	scn := bufio.NewScanner(os.Stdin)
	scn.Split(bufio.ScanWords)
	nextInt := func() int { scn.Scan(); r, _ := strconv.Atoi(scn.Text()); return r }
	w := bufio.NewWriter(os.Stdout)

	n := nextInt()
	vecs := make([][]int, n)
	for i := 0; i < n; i++ {
		u := nextInt()
		k := nextInt()
		for j := 0; j < k; j++ {
			vecs[u-1] = append(vecs[u-1], nextInt()-1)
		}
	}

	ds := make([]int, 0, n)
	for i := 0; i < n; i++ {
		ds = append(ds, -1)
	}

	q := make([]int, 0, n)
	q = append(q, 0)
	ds[0] = 0

	for len(q) > 0 {
		i := pop(&q)
		for _, v := range vecs[i] {
			if ds[v] == -1 {
				ds[v] = ds[i]+1
				q = append(q, v)
			}
		}
	}

	for i, d := range ds {
		fmt.Fprintln(w, i+1, d)
	}

	w.Flush()
}

func pop(q *[]int) int {
	v := (*q)[0]
	*q = (*q)[1:]
	return v
}

Python: # -*- coding: utf-8 -*-
"""
Created on Sun Jul  8 10:56:33 2018

@author: maezawa
"""
n = int(input())
adj = [[] for _ in range(n)]
d = [-1 for _ in range(n)]
d[0] = 0


for j in range(n):
    ain = list(map(int, input().split()))
    u = ain[0]
    k = ain[1]
    for i in range(k):
        adj[u-1].append(ain[i+2]-1)
    adj[u-1].sort()
    #print(*adj[u-1])

stack = [0]

while stack:
    #print(stack)
    current = stack[-1]
    flag = 0
    for k in adj[current]:
        if d[k] < 0:
            d[k] = d[current]+1
            stack.append(k)
            flag = 1
        elif d[k] > d[current]+1:
            d[k] = d[current]+1
            stack.append(k)
            flag = 1
    if flag == 0:
        stack.pop()

    #print('current = {}, t = {}'.format(current, t))
    #print('stack', *stack)

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

Python: # -*- coding: utf_8 -*-

level = False
def debug(v):
    if level:
        print(v)

NOT_FOUND = 0
ENQUEUED = 1
FOUND = 2

def bfs(graph, status, results):
    queue = []
    queue.append(1)
    while len(queue) != 0:
        node = queue.pop(0)
        status[node] = FOUND
        d = results[node]
        for edge in graph[node]:
            if status[edge] != NOT_FOUND:
                continue
            status[edge] = ENQUEUED
            queue.append(edge)
            results[edge] = d + 1

    return results

if __name__ == "__main__":
    n = int(input())
    status = [NOT_FOUND] * (n + 1)
    results = [-1] * (n + 1)
    results[1] = 0
    g = [[0]]

    for i in range(n):
        row = [int(x) for x in input().split()]
        row.pop(0)
        row.pop(0)
        g.append(row)

    bfs(g, status, results)
    results.pop(0)

    for idx, v in enumerate(results):
        print(idx + 1, v)

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

import sys
from collections import deque

UNVISITED, VISITED_IN_QUEUE, POPPED_OUT = 0, 1, 2


def generate_adj_matrix(v_info):
    for v_detail in v_info:
        v_adj_list = v_detail[2:]
        # assert len(v_adj_list) == int(v_detail[1])
        for each in v_adj_list:
            init_adj_matrix[int(v_detail[0]) - 1][int(each) - 1] = 1
    return init_adj_matrix


def graph_bfs(v_init):
    vertices_status_list[v_init] = VISITED_IN_QUEUE
    vertices_distance_list[v_init] = 0
    vertices_visit_queue.appendleft(v_init)

    while vertices_visit_queue:
        current_vertex = vertices_visit_queue.popleft()
        for v in range(1, vertices_num + 1):
            if adj_matrix[current_vertex - 1][v - 1] and vertices_status_list[v] is UNVISITED:
                vertices_status_list[v] = VISITED_IN_QUEUE
                vertices_distance_list[v] = vertices_distance_list[current_vertex] + 1
                vertices_visit_queue.append(v)
        vertices_status_list[current_vertex] = POPPED_OUT
    return vertices_distance_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    vertices_info = list(map(lambda x: x.split(), _input[1:]))
    init_adj_matrix = [[0] * vertices_num for _ in range(vertices_num)]
    # assert len(vertex_info) == vertex_num

    # config length = (vertex_num + 1)
    vertices_visit_queue = deque()
    vertices_status_list = [UNVISITED] * vertices_num
    vertices_status_list.insert(0, -1)
    vertices_distance_list = [-1] * (vertices_num + 1)

    adj_matrix = generate_adj_matrix(vertices_info)
    ans = graph_bfs(v_init=1)
    for j in range(vertices_num):
        print(j + 1, ans[j + 1])

Python: n = int(input())
graph = [[0 for i in range(n)] for j in range(n)]
d = [0] * n
f = [0] * n
queue = [0]


for i in range(n):
   a = list(map(int, input().split()))
   for j in range(0, a[1], 1):
       graph[a[0] - 1][a[2 + j] - 1] = 1

while len(queue) != 0:
    i = queue.pop(0)
    for j in range(n):
        if (graph[i][j] == 1) & (f[j] == 0):
            queue.append(j)
            f[j] = 1
            d[j] = d[i] + 1

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

Python: import queue
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])

Python: from collections import defaultdict, deque

N = int(input())
edges = {}
scores = defaultdict(lambda: -1)

for _ in range(N):
    l = list(map(int, input().split()))
    node = l[0]
    degree = l[1]
    edges[node] = l[2:]

q = deque()
q.append((1, 0))

while q:
    node, score = q.popleft()
    if scores[node] != -1:
        continue
    scores[node] = score
    for child in edges[node]:
        q.append((child, score+1))

for node in range(1, N+1):
    print('%d %d' % (node, scores[node]))

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

while Q:top = Q[0];func(top);del Q[0]
    
for i in range(1,N):
    if int(L[i]) == 0:
        L[i] = -1

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

Python: #coding:utf-8
n = int(input())
Q = [1]
M = [[False for i in range(n)] for j in range(n)]
dataList = []
for i in range(n):
    data = list(map(int,input().split()))
    dataList.append(data)
    for j in range(data[1]):
        v = data[j+2] - 1
        M[i][v] = True
color = ["white" for i in range(n)]
d = [-1 for i in range(n)]
d[0] = 0
while Q != []:
    u = Q.pop(0) - 1
    color[u] = "gray"
    data = dataList[u]
    for i in range(data[1]):
        v = data[i+2] - 1
        if M[u][v] == True and color[v] == "white":
            color[v] = "gray"
            d[v] = d[u] + 1
            Q.append(v+1)
    color[u] = "black"

for i,j in enumerate(d,1):
    print(i,j)

Python: from collections import deque

n = int(input())
graphs = [[] for i in range(n+1)]
visited = [False] * (n+1)
min_s = [-1] * (n+1)

for i in range(1, n+1):
    nodes = list(map(int, input().split()))
    graphs[i].extend(nodes[1:])

q = deque()
q.append([1, 0])
while q:
    node, j = q.popleft()
    if not visited[node]:
        visited[node] = True
        min_s[node] = j
    nodes = graphs[node]
    for node in nodes:
        if not visited[node]:
            q.append([node, j+1])

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

Python: n=int(input())
G=[]
for i in range(n):
    u,k,*l=map(int,input().split())
    G.append(l)
#print(G)

#BFS
from collections import deque
def bfs(G,v,p):
    que=deque()
    que.append((v,p))
    log=[-1]*n
    log[0]=0
    while que:
        #queの先頭を取り出す
        V,P=que.popleft()
        for next_v in G[V-1]:
            if log[next_v-1]!=-1:continue
            log[next_v-1]=log[V-1]+1
            que.append((next_v,V))
    return log

log=bfs(G,1,-1)
for i in enumerate(log,1):
    print(*i)