Go: package main

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

const MAX = 1000
const NIL = -1

type Node struct {
	id    int
	depth int
}

type Queue struct {
	head      int
	tail      int
	container [MAX]Node
}

func (q *Queue) inQueue(x Node) {
	q.container[q.tail] = x
	q.tail = (q.tail + 1) % MAX
}

func (q *Queue) deQueue() Node {
	x := q.container[q.head]
	q.head = (q.head + 1) % MAX
	return x
}

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

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()
	route := make([][]int, n)
	for i := range route {
		u, k := scanInt(), scanInt()
		u--
		route[u] = make([]int, k)
		for j := range route[u] {
			num := scanInt()
			num--
			route[i][j] = num
		}
	}

	d := make([]int, n)
	for i := range d {
		d[i] = NIL
	}

	start := Node{0, 0}
	que := Queue{}
	que.inQueue(start)
	for !que.isEmpty() {
		node := que.deQueue()
		if d[node.id] != NIL {
			continue
		}
		d[node.id] = node.depth

		for _, nextId := range route[node.id] {
			next := Node{id: nextId, depth: node.depth + 1}
			que.inQueue(next)
		}
	}

	for i, depth := range d {
		fmt.Println(i+1, depth)
	}
}

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

Python: N= int(input())
E = [input().split()[2:] for _ in range(N)]
Q = [0]
L = [0] + [-1]*N
frag = [1] + [0]*N
def func(ide):
    global Q
    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:pass
    

while Q:top = Q[0];func(top);del Q[0]

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

Python: import sys
from collections import deque

sys.setrecursionlimit(50000)

n = int(input())

data = [[] for _ in range(n)]
answer = [-1]*n
answer[0] = 0
for i in range(n):
    line = list(map(int, input().split(" ")))
    if line[1] != 0:
        for e in line[2:]:
            data[i].append(e)


def bfs(vs, count=0):
    next_vs = []
    for v in vs:
        for n_v in data[v-1]:
            if answer[n_v-1] == -1:
                answer[n_v-1] = count+1
                next_vs.append(n_v)
    if not next_vs == []:
        bfs(next_vs, count+1)


bfs([1])

for i in range(n):
    line = str(i+1) + " " + str(answer[i])
    print(line)