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

Python: N= int(input())
E = [input().split()[2:] for _ in [0]*N]
Q = [0]
L = [0] + [-1]*N
def func(ide):
    global Q
    for i in E[ide]:
        i = int(i) - 1
        if L[i] < 0 :L[i] = L[ide] +1 ;Q += [i]
    

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

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

Python: from collections import deque
n = int(input())
graph = [[] for _ in range(n)]
global Q, S, T
global visited, dis
Q = deque([0])
S = [0] #訪れた順
T = []
visited = [0 for _ in range(n)]
dis = [-1 for _ in range(n)] #初めからの距離
visited[0] = 1
dis[0] = 0
def input_graph(n):
  for _ in range(n):
    node_id, num, *v = list(map(int, input().split()))
    for i in range(num):
      graph[node_id-1].append(v[i]-1)

def bfs(node_id):
  global Q, S
  while Q:
    node_id = Q.popleft()

    for ad_node in graph[node_id]:
      if visited[ad_node] == 1:
        continue
      visited[ad_node] = 1
      dis[ad_node] = dis[node_id] + 1
      S.append(ad_node)
      Q.append(ad_node)

if __name__ == "__main__":
  input_graph(n)
  bfs(0)
  for i, d in enumerate(dis):
    print(i+1, d)

Python: INF = float('inf')

v = int(input())
graph = [None]

for i in range(v):
    u = list(map(int, input().split()))
    
    graph.append(u[2:])

visited = [False] * (v+1)
visited[1] = True
cost = [INF] * (v+1)
cost[1] = 0
c = 0

q = graph[1]

while q:
    c += 1
    q_next = []
    for u in q:
        if not visited[u]:
            visited[u] = True
            cost[u] = c
            q_next.extend(graph[u])
    q = q_next
    
for i in range(v):
    if cost[i+1] == INF: cost[i+1] = -1
    print(i+1, cost[i+1])

Python: from collections import deque
N=int(input())
color=["white"]*(N+1)
rinsetu=[[] for i in range(N+1)]
for i in range(N):
    a,*b=list(map(int,input().split()))
    for idx,j in enumerate(b):
        if idx==0:continue
        rinsetu[a].append(j)
distance=[10**5]*(N+1)
distance[1]=0
def bfs():
    d = deque()
    d.append(1)
    while(d):
        num=d.popleft()
        color[num] = "black"
        for i in rinsetu[num]:
            if color[i]=="white":
                d.append(i)
                distance[i]=min(distance[num]+1,distance[i])

bfs()
for i in range(1,N+1):
    if distance[i]==10**5:distance[i]=-1
    print(i,distance[i])

Python: N= int(input())
E = [input().split()[2:] for _ in [0]*N]
Q = [0]
L = [0] + [-1]*N

    


while Q:
    top = Q.pop(0)
    for i in E[top]:
        i = int(i) - 1
        if L[i] < 0 :L[i] = L[top] +1 ; Q+= [i]

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

Python: n = int(input())
l = [[] for i in range(n)]
retval=[10**10 for i in range(n)]



for i in range(n):
    _input = [int(j) - 1 for j in input().split(" ")]
    u = _input[0]
    k = _input[1] + 1
    node = sorted(_input[2::])
    if u in node:
        node.remove(u)
    l[u] = node

retval[0]=0
for step in range(n+1):
    for i ,d in enumerate(retval):
        if d==step:
            for node in l[i]:
                retval[node]=min(retval[node],step+1)

for i,d in enumerate(retval):
    if d==10**10:
        print(i+1,-1)
    else:
        print(i+1,d)

Python: # 幅優先探索 Breadth first search: BFS
import queue

n = int(input())
Adj = [[] for i in range(n)]
for i in range(n):
    dat = [int(i) for i in input().split()]
    Adj[dat[0] - 1] = dat[2:]

D = [-1 for i in range(n)]
D[0] = 0
Q = queue.Queue()
Q.put(1)
while not Q.empty():
    u = Q.get()
    for v in Adj[u - 1]:
        if D[v - 1] == -1:
            Q.put(v)
            D[v - 1] = D[u - 1] + 1

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

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 sys
import queue
input = sys.stdin.readline
n = int(input())
g = [[] for _ in range(n+1)]
d = [-1 for _ in range(n+1)]
for _ in range(n):
    c = list(map(int,input().split()))
    g[c[0]] = c[2:]

depth = 0
q = queue.Queue()
p = queue.Queue()
q.put(1)
while not q.empty():
    while not q.empty():
        s = q.get()
        if d[s] < 0:
            d[s] = depth
            for i in g[s]:
                p.put(i)
    p, q = q, p
    depth += 1

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