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: # Breadth First Search
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
E = (tuple(map(int, input().split())) for _ in range(n))
E = [[v-1 for v in V] for i, k, *V in E]

q = deque()
visited = [False]*n
D = [-1]*n

# 初期条件
s = 0
q.append(s)
visited[s] = True
D[s] = 0

# BFS
while q:
    v = q.popleft()
    for u in E[v]:
        if not visited[u]:
            q.append(u)
            visited[u] = True
            D[u] = D[v]+1


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

Python: from collections import deque

def main():
    n = int(input())
    _next = [[] for _ in range(n)]
    for _ in range(n):
        u, k, *v = map(lambda s: int(s) - 1, input().split())
        _next[u] = v
    queue = deque()
    queue.append(0)
    d = [-1] * n
    d[0] = 0
    while queue:
        u = queue.popleft()
        for v in _next[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                queue.append(v)
    for i, v in enumerate(d, start=1):
        print(i, v)


if __name__ == '__main__':
    main()

Python: N = int(input())

tree = [[] for _ in range(N)]

for _ in range(N):
    u, k, *v = map(int, input().split())
    tree[u-1] = v

ans = [float('inf') for _ in range(N)]
ans[0] = 0

from collections import deque

q = deque([(0, 0)])

while q:
    p, d = q.popleft()
    for c in tree[p]:
        if ans[c-1] > d+1:
            ans[c-1] = d+1
            q.append((c-1, d+1))

for i in range(N):
    if ans[i] == float('inf'):
        print(i+1, -1)
    else:
        print(i+1, ans[i])

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 != []:
    print(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":
            d[v] = d[u] + 1
            Q.append(v+1)
    color[u] = "black"

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

Python: #!/usr/bin/python3

def find(id, V, d, dist):
    i = id - 1
    dist[i] = d
    for v in V[i]:
        if dist[v - 1] == -1 or dist[v - 1] > d + 1:
            find(v, V, d + 1, dist)
    
n = int(input())
# [isFind, d, f]
A = [[False, 0, 0] for i in range(n)]
U = []
V = []
dist = [-1] * n
for i in range(n):
    l = list(map(int, input().split()))
    U.append(l[0])
    V.append(l[2:])

find(1, V, 0, dist)

for u in U:
    print(u, dist[u - 1])

Python: import queue
N=int(input())
M=[list(map(int,input().split()[2:]))for _ in[0]*N]
q=queue.Queue();q.put(0)
d=[-1]*N;d[0]=0
while q.qsize()>0:
 u=q.get()
 for v in M[u]:
  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 deque

n = int(input())
adj = [[] for _ in range(n)]

for i in range(n):
  u,k,*v = map(int, input().split())
  v = [w-1 for w in v]
  adj[u-1].extend(v)

queue = deque([0])
ans = [-1] * n
ans[0] = 0

while queue:
  now = queue.popleft()
  
  for u in adj[now]:
    if ans[u] < 0:# 未訪問
      ans[u] = ans[now] + 1
      queue.append(u)

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

Python: N = int(input())
L = [[] for i in range(N+1)]
d = [-1] * (N+1)
f = [0] * (N+1)
nkey = []
ntime = []


def bfs():
    while len(nkey):
        key = nkey.pop(0)
        time = ntime.pop(0)
        if d[key] == -1:
            d[key] = time
        for i in range(len(L[key])):
            if d[L[key][i]] == -1:
                nkey.append(L[key][i])
                ntime.append(time+1)
        

for i in range(N):
    Q = list(map(int, input().split()))
    L[Q[0]].extend(Q[2:])

nkey.append(1)
ntime.append(0)
bfs()


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

Python: n=int(input())
a=[]
from collections import deque as dq
for i in range(n):
	aaa=list(map(int,input().split()))
	aa=aaa[2:]
	a.append(aa)
dis=[-1]*n
dis[0]=0
queue=dq([0])
while queue:
	p=queue.popleft()
	for i in range(len(a[p])):
		if dis[a[p][i]-1]==-1:
			queue.append(a[p][i]-1)
			dis[a[p][i]-1]=dis[p]+1
for i in range(n):
	print(i+1,dis[i])

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

visited = [False]*n
dislis = [n+1]*n
Q = [[1,0]]

def pull():
    return Q.pop(0)

def push(x):
    Q.append(x)

while len(Q)>0:
    cur = pull()
    curpoint = cur[0]
    count = cur[1]
    if not visited[curpoint-1]:
        visited[curpoint-1]=True
        dislis[curpoint-1] = count
        for i in adjlis[curpoint-1]:
            push([i,count+1])


for i in range(n):
    if dislis[i]==n+1:
        dislis[i] = -1
    print(i+1,dislis[i])

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

f[0] = 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] if (i == 0) | (d[i] != 0) else -1) for i in range(n)]

Python: import sys
from collections import defaultdict
from queue import Queue


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    g = defaultdict(list)
    for i in range(n):
        line = list(map(int, input().split()))
        if line[1] > 0:
            g[line[0]] = line[2:]
    q = Queue()
    q.put(1)
    dist = [-1] * (n + 1)
    dist[1] = 0
    while not q.empty():
        p = q.get()
        for nxt in g[p]:
            if dist[nxt] == -1:
                dist[nxt] = dist[p] + 1
                q.put(nxt)
    for i in range(1, n + 1):
        print(i, dist[i])


if __name__ == "__main__":
    main()