Go: package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

func stringifyArray(arr []int) string {
	return strings.TrimRight(fmt.Sprintf("%+v", arr)[1:], "]")
}

var infty = 1000000000

type nodeKey int

type DirectedGraphNode struct {
	key       nodeKey
	adjacents []*DirectedGraphNode
	visited   bool
	d         int
	parent    *DirectedGraphNode
}

type DirectedGraph struct {
	nodes []DirectedGraphNode
}

func (g *DirectedGraph) setAdjacency(l, r nodeKey) {
	g.nodes[l].adjacents = append(g.nodes[l].adjacents, &g.nodes[r])
}

func newDirectedGraph(nNodes int) *DirectedGraph {
	graph := DirectedGraph{}
	graph.nodes = make([]DirectedGraphNode, nNodes)
	for iNodes := 0; iNodes < nNodes; iNodes++ {
		graph.nodes[iNodes].key = nodeKey(iNodes)

		graph.nodes[iNodes].visited = false
		graph.nodes[iNodes].d = infty
		graph.nodes[iNodes].parent = nil
	}
	return &graph
}

type QueueEntry struct {
	node *DirectedGraphNode
	next *QueueEntry
}

type Queue struct {
	head, tail *QueueEntry
}

func (q *Queue) enqueue(node *DirectedGraphNode) {
	entry := QueueEntry{}
	entry.node = node

	if q.tail == nil {
		q.head = &entry
		q.tail = &entry
		return
	}

	q.tail.next = &entry
	q.tail = q.tail.next
}

func (q *Queue) dequeue() *QueueEntry {
	if q.head == nil {
		return nil
	}
	poped := q.head
	q.head = q.head.next
	if q.head == nil {
		q.tail = nil
	}
	return poped
}

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

func fillDistancesByBreadthFirstSearch(g *DirectedGraph, startNode *DirectedGraphNode) {
	startNode.visited = true
	startNode.d = 0

	queue := Queue{}
	queue.enqueue(startNode)
	for !queue.isEmpty() {
		u := queue.dequeue().node
		for _, adjacent := range u.adjacents {
			if !adjacent.visited {
				adjacent.visited = true
				adjacent.d = u.d + 1
				adjacent.parent = u
				queue.enqueue(adjacent)
			}
		}
		u.visited = true
	}
}

func main() {
	scanner.Split(bufio.ScanWords)

	nNodes := nextInt()
	g := newDirectedGraph(nNodes + 1)

	for iNode := 0; iNode < nNodes; iNode++ {
		nodeKeyLeft := nodeKey(nextInt())
		nAdj := nextInt()
		for iAdj := 0; iAdj < nAdj; iAdj++ {
			nodeKeyRight := nodeKey(nextInt())
			g.setAdjacency(nodeKeyLeft, nodeKeyRight)
		}
	}

	// fmt.Println(g)
	fillDistancesByBreadthFirstSearch(g, &g.nodes[1])
	// fmt.Println(g)

	for iNode := 1; iNode <= nNodes; iNode++ {
		node := g.nodes[iNode]
		distance := node.d
		if distance == infty {
			distance = -1
		}
		fmt.Println(node.key, distance)
	}
}

Python: import queue

n = int(input())
v = [[]]
for _ in range(n):
    edges = sorted([int(x) for x in input().split()][2:])
    v.append(edges)
answers = [[idx, -1] for idx in range(n + 1)]
q = queue.Queue()
q.put(1)

answers[1][1] = 0
while not q.empty():
    node = q.get()
    for next_node in v[node]:
        if answers[next_node][1] != -1:
            continue
        q.put(next_node)
        answers[next_node][1] = answers[node][1] + 1

for idx, time in answers[1:]:
    print(idx, time)

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] != -1 : continue
            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())
G = [None for i in range(N)]
for i in range(N):
    u, k, *vs = map(int, input().split())
    G[u-1] = [e-1 for e in vs]


from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

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

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