Go: package main

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

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Scan()
	num, _ := strconv.Atoi(sc.Text())
	nodes := make(map[int]*node)

	for i := 0; i < num; i++ {
		sc.Scan()
		id, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		nodeNum, _ := strconv.Atoi(sc.Text())
		n := node{id, make([]int, 0), -1}
		for j := 0; j < nodeNum; j++ {
			sc.Scan()
			nid, _ := strconv.Atoi(sc.Text())
			n.nexts = append(n.nexts, nid)
		}
		nodes[id] = &n
	}
	nodes[1].depth = 0

	walk(1, 0, &nodes)
	for i := 1; i < len(nodes)+1; i++ {
		fmt.Printf("%v %v\n", (*nodes[i]).id, (*nodes[i]).depth)
	}
}

var time int
var record [100][100]bool
var q Queue

func walk(nid int, from int, nodes *map[int]*node) {
	q.Enqueue((*nodes)[nid])
	for !q.IsEmpty() {
		n := q.Dequeue().(*node)
		for _, v := range n.nexts {
			n2 := (*nodes)[v]
			if n2.depth != -1 {
				continue
			}
			n2.depth = n.depth + 1
			q.Enqueue((*nodes)[v])
		}
	}
}

type node struct {
	id    int
	nexts []int
	depth int
}

// Queue is Queue
type Queue struct {
	val []interface{}
}

// Enqueue value
func (queue *Queue) Enqueue(val interface{}) {
	queue.val = append(queue.val, val)
}

// Dequeue value
func (queue *Queue) Dequeue() interface{} {
	res := queue.val[0]
	queue.val = queue.val[1:len(queue.val)]
	return res
}

// IsEmpty return true when queue is empty
func (queue *Queue) IsEmpty() bool {
	return len(queue.val) == 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]))