Go: package main

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

type AdjacentList struct {
	matrix [][]int
}

func NewEmptyAdjacentList(dim int) *AdjacentList {
	matrix := make([][]int, dim)
	for i := 0; i < dim; i++ {
		matrix[i] = make([]int, dim)
	}
	return &AdjacentList{matrix: matrix}
}

func (al *AdjacentList) set(node int, adjacent int) {
	al.matrix[node-1][adjacent-1] = 1
}

func (al *AdjacentList) findAdjacentsFor(node int) []int {
	adjacents := []int{}
	for i, v := range al.matrix[node-1] {
		if v == 1 {
			adjacents = append(adjacents, i+1)
		}
	}
	return adjacents
}

type DistanceList struct {
	list []int
}

func NewDistanceList(dim int) *DistanceList {
	list := make([]int, dim)
	for i := 0; i < dim; i++ {
		list[i] = -1
	}
	return &DistanceList{list: list}
}

func (dl *DistanceList) set(node int, distance int) {
	dl.list[node-1] = distance
}

func (dl *DistanceList) get(node int) int {
	return dl.list[node-1]
}

func (dl *DistanceList) isVisited(node int) bool {
	return dl.list[node-1] >= 0
}

type Position struct {
	node     int
	distance int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	dim, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	al := NewEmptyAdjacentList(dim)

	for i := 1; i <= dim; i++ {
		node, err := nextInt(sc)
		if err != nil {
			panic(err)
		}

		adjacentNum, err := nextInt(sc)
		if err != nil {
			panic(err)
		}
		for j := 0; j < adjacentNum; j++ {
			adjacent, err := nextInt(sc)
			if err != nil {
				panic(err)
			}
			al.set(node, adjacent)
		}
	}

	dl := NewDistanceList(dim)

	bfs(al, dl)

	for i := 1; i <= dim; i++ {
		fmt.Printf("%d %d\n", i, dl.get(i))
	}
}

func bfs(al *AdjacentList, dl *DistanceList) {
	stack := []Position{Position{node: 1, distance: 0}}
	for len(stack) > 0 {
		currentPosition := stack[0]
		stack = stack[1:]
		if !dl.isVisited(currentPosition.node) {
			dl.set(currentPosition.node, currentPosition.distance)
		}
		for _, v := range al.findAdjacentsFor(currentPosition.node) {
			if !dl.isVisited(v) {
				stack = append(stack, Position{node: v, distance: currentPosition.distance + 1})
			}
		}
	}
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

Python: from __future__ import print_function
import time
from sys import stdin
from Queue import Queue
start = time.clock()
i = 0
num=int(stdin.readline())
L=[]
for _ in range(num):
    L.append([int(s) for s in stdin.readline().split()[2:]])
 
d=[-1]*num
d[0]=0
q=Queue(100)
q.put(0)
while not q.empty():
    u=q.get()
    for v in L[u]:
        if d[v-1]<0:
            d[v-1]=d[u]+1
            q.put(v-1)
for i,v in enumerate(d):
    print (i+1,)

Python: from collections import deque

N = int(input())

edge = [[] for _ in range(N)]
for _ in range(N):
    t = list(map(int,input().split()))
    if t[1] != 0:
        edge[t[0]-1] = list(map(lambda x:int(x)-1, t[2:]))

dist = [-1]*N
dist[0] = 0
        
q = deque([0])
while q:
    now = q.popleft()
    for nxt in edge[now]:
        if dist[nxt] == -1:
            dist[nxt] = dist[now] + 1
            q.append(nxt)
        else:
            dist[nxt] = min(dist[nxt], dist[now] + 1)

for i,d in enumerate(dist):
    print(i+1, d)

Python: import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

def bfs(start):
    d = [-1]*n
    d[start] = 0
    q = collections.deque([start])
    while q:
        p = q.popleft()
        next_v = edge[p]
        for v in next_v:
            if d[v] == -1:
                q.append(v)
                d[v] = d[p] + 1
    return d

if __name__ == "__main__":
    n = int(input())
    edge = []
    for i in range(n):
        u,k,*v_li = map(int,input().split())
        u-=1
        for j in range(len(v_li)):
            v_li[j] -= 1
        edge.append(v_li)
    ans = bfs(0)
    for i in range(n):
        print(i+1,ans[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)

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

Python: from collections import deque
import sys
read = sys.stdin.read
readline = sys.stdin.readline


def main():
    n = int(readline())

    E = [[]]
    for _ in range(n):
        u,k,*v = map(int, readline().split())
        E.append(v)

    d = [-1] * (n+1)
    
    queue = deque([1])
    d[1] = 0
    while queue:
        v = queue.popleft()
        for e in E[v]:
            if d[e] == -1:
                d[e] = d[v] + 1
                queue.append(e)

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


if __name__ == "__main__":
    main()

Python: n = int(input())
a = [[False]*n for i in range(n)]
   
for i in range(n):
    v = list(map(int, input().split()))
    u = v[0]
    k = v[1]
    for j in range(k):
        a[u - 1][v[2 + j] - 1] = True

isDiscovered = [False] * n
distance = [0]*n
 
def dfs(x, d):
    isDiscovered [x] = True
    distance[x] = d
    for i in range(n):
        if a[x][i] and not isDiscovered[i]:
            dfs(i, d+1)

 
for i in range(n):
    if not isDiscovered[i]:
        dfs(i, 1)
 
for i in range(n):
    print(i+1, distance[i])

Python: n = int(input())
adj = [list(map(int, input().split()))[2:] for _ in range(n)]

d = [-1] * n

s = 1
q = []
d[s - 1] = 0
q.append(s)
while len(q):
    u = q.pop()
    v = adj[u - 1]
    for vi in v:
        if d[vi - 1] == -1:
            d[vi - 1] = d[u - 1] + 1
    q += v


for i, di in enumerate(d):
    print(i + 1, di)

Python: from collections import deque

n = int(input())
AL = [None for _ in range(n + 1)]
for i in range(1, n + 1):
    ukv = [int(x) for x in input().split()]
    AL[ukv[0]] = ukv[2:]

que = deque([1])
visited = [False] + [True] + [False] * (n - 1)
dist = [-1] + [0] + [-1] * (n - 1)
while que:
    u = que.popleft()
    for v in AL[u]:
        if visited[v]: continue
        dist[v] = dist[u] + 1
        visited[v] = True
        que.append(v)

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

Python: import collections,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
n = I()
ukv = [LI() for _ in range(n)]
graph = {i:collections.deque() for i in range(1,n+1)} #1_indexed
for x in ukv:
    u,k,*v = x
    for y in v:
        graph[u].append(y)
seen = [0]*(n+1) #1_indexed
min_dist = [-1]*(n+1) #1_indexed
queue = collections.deque() #頂点NOを入れておく
def bfs():
    seen[1] = 1
    queue.append(1)
    min_dist[1] = 0
    while queue:
        q_NO = queue.popleft()
        q_dist = min_dist[q_NO]
        if not graph[q_NO]:
            continue
        g = graph[q_NO]
        for _ in range(len(g)):
            g_NO = g.popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            queue.append(g_NO)
            min_dist[g_NO] = q_dist+1
bfs()
for i,ans in enumerate(min_dist[1:],1):
    print(i,ans)