Go: package main

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

var distance []int

type queue struct {
	q    []int
	head int
	tail int
}

func (q *queue) push(n int) {
	q.q[q.tail] = n
	q.tail++
}

func (q *queue) pop() int {
	q.head++
	return q.q[q.head-1]
}

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

func makeAdjList() [][]int {
	var n int
	fmt.Scanf("%d", &n)

	adj := make([][]int, n)
	for i := 0; i < n; i++ {
		adj[i] = make([]int, n)
	}

	sc := bufio.NewScanner(os.Stdin)
	for i := 0; i < n; i++ {
		sc.Scan()
		nodeInfo := strings.Split(sc.Text(), " ")
		outDegree, _ := strconv.Atoi(nodeInfo[1])

		if outDegree > 0 {
			for k := 0; k < outDegree; k++ {
				j, _ := strconv.Atoi(nodeInfo[k+2])
				j-- // convert 1 based to 0 based
				adj[i][j] = 1
			}
		}
	}

	return adj
}

func bfs(graph [][]int, s int) {
	distance = make([]int, len(graph))

	infty := -1
	for i := 0; i < len(distance); i++ {
		distance[i] = infty
	}
	distance[s] = 0

	q := &queue{make([]int, 1000), 0, 0}
	q.push(s)

	for !q.isEmpty() {
		u := q.pop()
		for i := 0; i < len(graph); i++ {
			if graph[u][i] == 0 {
				continue // u, i間に辺がない場合
			}
			if distance[i] != infty {
				continue // 訪問済みの場合
			}
			// 訪問するnodeの始点からの距離を設定し、訪問キューに入れる
			distance[i] = distance[u] + 1
			q.push(i)
		}
	}

	// print distance
	for i, d := range distance {
		fmt.Printf("%d %d\n", i+1, d)
	}
}

func main() {
	adj := makeAdjList()
	bfs(adj, 0)
}

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)

Python: n = int(input())

m = [[0 for _ in range(n+1)] for _ in range(n+1)]
mm = [[] for _ in range(n+1)]

for _ in range(n):
	tmp = [int(x) for x in input().split()]
	u,k,l = tmp[0],tmp[1],tmp[2:]
	mm[u] = tmp[2:]
	for x in l:
		m[u][x] = 1
		
dp = [float('inf') for _ in range(n+1)]
queue = [1]

while queue:
	t = queue.pop(0)
	for x in mm[t]:
		if dp[x] > dp[t] + 1:
			dp[x] = dp[t] + 1
			queue.append(x)
		else:
			pass
			
for i,x in enumerate(queue):
	if i == 0:
		pass
	else:
		if x == float('inf'):
			print(i, -1)
		else:
			print(i, x)

Python: from collections import deque

n = int(input())
g = [None] * n
visited = [0] * n
dist = [-1] * n
queue = deque()

while n:
    l = list(map(int, input().split()))
    connected = [i - 1 for i in l[2:]]
    g[l[0] - 1] = [i - 1 for i in l[2:]]
    n -= 1

queue.append((0, 0))
visited[0] = 1

while queue:
    i, d = queue.popleft()
    dist[i] = d
    for c in g[i]:
        if not visited[c]:
            visited[c] = 1
            queue.append((c, d + 1))

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

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)]
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 in range(1, n + 1):
    print(i, d[i])

Python: from collections import deque


def bfs(s, m, n):
    d = []
    for _ in range(n):
        d.append(1 << 21)
    queue = deque()
    queue.append(s)
    d[s] = 0

    while len(queue) != 0:
        u = queue.popleft()
        for v in range(n):
            if m[u][v] == 0:
                continue
            if d[v] != 1 << 21:
                continue
            d[v] = d[u] + 1
            queue.append(v)

    for i, v in enumerate(d):
        ans_v = v
        if v == 1 << 21:
            ans_v = -1

        print(i + 1, ans_v)


n = int(input())
m = list()
for i in range(n):
    tmp = list()
    for j in range(n):
        tmp.append(0)
    m.append(tmp)

for _ in range(n):
    l = [int(i) for i in input().split()]
    u = l[0]
    for li in l[2:]:
        m[u - 1][li - 1] = 1

bfs(0, m, n)

Python: N= int(input())
E = [input().split()[2:] for _ in range(N)]
frag, T, L,Q = [0]*N, [0]*N,[0] + [-1]*N, [0]
frag[0] = 1
def func(ide):
    for i in E[ide]:
        i = int(i) - 1
        if L[i] < 0 :frag[i] = 1;L[i] = L[ide] +1 ;Q.append(i) 
        else:return

while Q:top = Q.pop();func(top)

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

Python: import queue

n = int(input())
graph = []
for _ in range(n):
    line = list(map(int, input().split()))
    graph.append([v - 1 for v in line[2:]])

q = queue.Queue()
q.put(0)
dist = [-1] * n
dist[0] = 0

while True:
    v = q.get()
    for next_v in graph[v]:
        if dist[next_v] == -1: 
            q.put(next_v)
            dist[next_v] = dist[v] + 1

    if q.empty():
        break

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

Python: n = int(input())

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

isSearched = [None] + [False] * n

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

import collections

def bfs(u):
    isSearched[u] = True
    distance[u] = 0
    edge = collections.deque()
    edge.append(u)
    while edge:
        c_e = edge.popleft()
        for n_e in adj[c_e]:
            if not isSearched[n_e]:
                isSearched[n_e] = True
                distance[n_e] = distance[c_e] + 1
                edge.append(n_e)


bfs(1)

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