Problem:
Breadth First Search Write a program which reads an directed graph $G = (V, E)$, and finds the shortest distance from vertex $1$ to each vertex (the number of edges in the shortest path). Vertices are identified by IDs $1, 2, ... n$. Input In the first line, an integer $n$ denoting the number of vertices, is given. In the next $n$ lines, adjacent lists of vertex $u$ are given in the following format: $u$ $k$ $v_1$ $v_2$ ... $v_k$ $u$ is ID of the vertex and $k$ denotes its degree.$v_i$ are IDs of vertices adjacent to $u$. Constraints  $1 \leq n \leq 100$  Output For each vertex $u$, print $id$ and $d$ in a line. $id$ is ID of vertex $u$ and $d$ is the distance from vertex $1$ to vertex $u$. If there are no path from vertex $1$ to vertex $u$, print -1 as the shortest distance. Print in order of IDs. Sample Input 1 4
1 2 2 4
2 1 4
3 0
4 1 3 Sample Output 1 1 0
2 1
3 2
4 1 Reference Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

Solution (Python):
from collections import deque


N = int(input())
DG = {}
for i in range(N):
    tmp = input().split()
    if int(tmp[1]) != 0:
        DG[i] = [int(x)-1 for x in tmp[2:]]
    else:
        DG[i] = []


result = {}
is_visited = {key: False for key in range(N)}


que = deque([(0, 0)])  
while que:
    nodeid, cost = que.popleft()  
    result[nodeid] = cost
    is_visited[nodeid] = True  
    for nextnode in DG[nodeid]:
        if is_visited[nextnode]:
            pass
        else:  
            que.append((nextnode, cost + 1))
            is_visited[nextnode] = True  

for i in range(N):
    if is_visited[i]:
        print(i + 1, result[i])
    else:
        print(i+1, -1)

Solution (Python):
from collections import deque

n = int(input())
g = []

ans = [-1] * n
done = set()
q = deque()

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



q.append(0)

ans[0] = 0
done.add(1)

while q:
    idx = q.popleft()
    adj = g[idx]
    

    for i in adj:
        if i not in done:
            ans[i-1] = ans[idx] + 1
            done.add(i)
            q.append(i-1)
    
    



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

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

Solution (Python):

import queue

WHITE = 0
GRAY = 1
BLACK = 2

NIL = -1
INF = 1000000000


def bfs(u):
    global Q
    Q.put(u)
    for i in range(n):
        d[i] = NIL
    d[u] = 0
    while not Q.empty():
        u = Q.get()
        for v in range(n):
            if (m[u][v] == 1) and (d[v] == NIL):
                d[v] = d[u] + 1
                Q.put(v)
n = int(input())

m = [[0 for i in range(n + 1)] for j in range(n + 1)]
vid = [0] * n
d = [0] * n
f = [0] * n
Q = queue.Queue()
color = [WHITE] * n
time = 0
nt = [0] * n

tmp = []
for i in range(n):
    nums=list(map(int,input().split()))
    tmp.append(nums)
    vid[i] = nums[0]

for i in range(n):
    for j in range(tmp[i][1]):
        m[i][vid.index(tmp[i][j + 2])] = 1

bfs(0)

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

Solution (Python):
if __name__ == '__main__':
    n = int(input())
    graph = [[0 for i in range(n)] for _ in range(n)]
    frist = [0 for _ in range(n)]
    end = [0 for _ in range(n)]
    visit = [False for _ in range(n)]
    
    for i in range(n):
        datas = [int(num) for num in input().split(' ')]
        if datas[1] > 0:
            for j in datas[2:]:
                graph[datas[0] - 1][j - 1] = 1

    queue = [0]
    visit = [False for _ in range(n)]
    visit[0] = True
    depths = [0 for _ in range(n)]
    while len(queue) != 0:
        point = queue.pop(0)
        for i in range(n):
            if graph[point][i] == 1 and visit[i] is False:
                queue.append(i)
                visit[i] = True
                depths[i] = depths[point] + 1
        if len(queue) == 0:
            for i in range(n):
                if visit[i] is False:
                    queue.append(i)
                    depths[i] = -1
                    visit[i] = True

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

Solution (Python):
n=int(input())
ps=[0 for j in range(n+1)]

for i in range(n):
    p,d,*vs=[int(j) for j in input().split()]
    ps[p]=vs
    
dist=[-1 for i in range(n+1)]    
    
d=0
queue=[1]

while queue:
    pos=queue.pop(0)
    if dist[pos] == -1:
        dist[pos]=d
    for i in ps[pos]:
        if dist[i]==-1:
            queue.append(i)
            dist[i]=dist[pos]+1

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

Solution (Python):

def bfs(s):  
    global n, M, color, d, q

    q.append(s)
    d[s] = 0

    while len(q) != 0:
        u = q.pop(0)

        for v in range(n):
            if M[u][v] != 1:
                continue

            if color[v] == 'WHITE':
                q.append(v)
                color[v] = 'GRAY'
                d[v] = d[u] + 1

        color[u] = 'BLACK'


n = int(input())

M = [[0 for i in range(n)] for j in range(n)]
color = ['WHITE'] * n  
d = [-1] * n  
q = []

for i in range(n):
    _ = list(map(int, input().split()))
    u = _[0] - 1  

    degree = _[1]
    for j in range(degree):
        v = _[j+2] - 1  
        M[u][v] = 1




bfs(0)

for i in range(n):
    print('{} {}'.format(i+1, d[i]))

Solution (Python):
from collections import deque
n=int(input())
E=[0]*n
for _ in range(n):
    u,k,*V=map(int,input().split())
    E[u-1]=V
d=[-1]*n
d[0]=0
todo=deque([1])
while todo:
    now=todo.popleft()
    for v in E[now-1]:
        if d[v-1]==-1:
            todo.append(v)
            d[v-1]=d[now-1]+1
for i in range(n):
    print(i+1,d[i])

Solution (Python):
from functools import lru_cache

@lru_cache(maxsize=None)
def solve(i, count):
    global ans
    global a
    if count >= N:
        return
    if ans[i][0] == -1:
        ans[i][0] = count
    elif ans[i][0] > count:
        ans[i][0] = count

    for x in range(a[i][1]):
        solve(a[i][2 + x] - 1, count + 1)


N = int(input())
a = []
for _ in range(N):
    a.append([int(x) for x in input().split()])

ans = [[-1 for i in range(1)] for j in range(N)]

solve(0, 0)

for i, x in enumerate(ans):
    print(i + 1, *x)

Solution (Python):
from collections import deque


def get_next_node(node, discovery_time, adj_mat):
    for i, node in enumerate(adj_mat[node]):
        if discovery_time[i] == 0 and node == 1:
            return i
    return None

def bfs(node, adj_mat):
    distances = [-1] * len(adj_mat)

    distances[node] = 0
    q = deque(maxlen=len(adj_mat))
    q.append(0)
    while q:
        visit_node = q.popleft()
        for j in range(len(adj_mat)):
            if adj_mat[visit_node][j] and distances[j]==-1:
                distances[j] = distances[visit_node] + 1
                q.append(j)
    
    for i, d in enumerate(distances):
        print(i+1, d)


if __name__ == "__main__":
    n_node = int(input())
    
    

    adjacency_mat = [[0 for i in range(n_node)] for j in range(n_node)]
    for i in range(n_node):
        command = list(map(int, input().split()))
        

        i = command.pop(0) - 1
        n_edge = command.pop(0)

        for j in command:
            adjacency_mat[i][j-1] = 1

    
    discovery_time = [0] * n_node
    finish_time = [0] * n_node
    bfs(0, adjacency_mat)

Solution (Python):
from collections import deque

N = 100
n = 0
M = None
WHITE = 0
GRAY = 1
BLACK = 2
INF = float('inf')
d = None


def main():
    global n, M, d
    M = [[0 for _ in range(N)] for _ in range(N)]
    n = int(input())
    d = [INF for _ in range(n)]

    for _ in range(n):
        u, k, *v_s = map(int, input().split(' '))
        for j in range(k):
            M[u-1][v_s[j-1]-1] = 1

    bfs()

    for i in range(n):
        print('{} {}'.format(i+1, d[i] if d[i] != INF else -1))


def bfs():
    q = deque()
    q.appendleft(0)
    d[0] = 0

    while len(q) > 0:
        u = q.pop()
        for v in range(n):
            if M[u][v] == WHITE:
                continue
            if d[v] != INF:
                continue
            d[v] = GRAY
            d[v] = d[u] + 1
            q.appendleft(v)


if __name__ == '__main__':
    main()

Solution (Python):




from collections import deque


N = int(input())
DG = {}
for i in range(N):
    tmp = input().split()
    if int(tmp[1]) != 0:
        DG[i] = [int(x)-1 for x in tmp[2:]]
    else:
        DG[i] = []


result = {}
is_visited = {key: False for key in range(N)}


que = deque([(0, 0)])  
while que:
    nodeid, cost = que.popleft()  
    result[nodeid] = cost
    is_visited[nodeid] = True  
    for nextnode in DG[nodeid]:
        if is_visited[nextnode]:
            pass
        else:  
            que.append((nextnode, cost + 1))
            is_visited[nextnode] = True  

for i in range(N):
    if is_visited[i]:
        print(i + 1, result[i])
    else:
        print(i+1, -1)

Solution (Python):

import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
from collections import deque

n=int(input())
G=[0]*n
memo=[0]*n
dis=[0]*n
dis[0]=1
que=deque()
que.append((0,1))

for i in range(n):
    inp=tuple(map(int,input().split()))
    G[inp[0]-1]=inp[2:]

while que:
    vertex,d=que.popleft()
    for v in G[vertex]:
        if not dis[v-1]:
            dis[v-1]=d+1
            que.append((v-1,d+1))
        

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

Solution (Python):
from collections import deque

N = int(input())
E = [None] * (N+1)
for _ in range(N):
    u, k, *vs = list(map(int, input().split()))
    E[u] = vs

d = [-1] * (N+1)
d[1] = 0
q = deque([(1, 0)])
while q:
    v, c = q.popleft()
    for u in E[v]:
        if d[u] < 0:
            d[u] = c+1
            q.append((u, c+1))

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

Solution (Python):
from typing import List
from collections import deque

def bfs(G: List[int], s: int) -> None:
	d[s] = 0
	color[s] = "GRAY"
	Q = deque()
	Q.append(s)
	while Q:
		u = Q.popleft()
		for v in G[u]:
			if color[v] == "WHITE":
				color[v] = "GRAY"
				d[v] = d[u] + 1
				pi[v] = u
				Q.append(v)
		color[u] = "BLACK"


if __name__ == "__main__":
	n = int(input())
	G = [[] for _ in range(n)]
	for _ in range(n):
		u, k, *adj = list(map(int, input().split()))
		u -= 1
		G[u] = [v - 1 for v in adj]
	color = ["WHITE" for _ in range(n)]
	d = [-1 for _ in range(n)]
	pi = [None for _ in range(n)]
	bfs(G, 0)
	for i in range(n):
		print(f"{i + 1} {d[i]}")

Solution (Python):
from collections import deque
from enum import Enum

class Color(Enum):
  WHITE = 0
  GRAY = 1
  BLACK = 2


N = int(input())
adj = [list(map(int, input().split()))[2:] for i in range(N)]


colors = [Color.WHITE for i in range(N)]
INF = N
d = [-1 for i in range(N)]
d[0] = 0

q = deque()
q.append(1)
colors[0] == Color.GRAY
while len(q) > 0:
  u = q.popleft()-1
  for v in adj[u]:
    v -= 1
    if colors[v] != Color.WHITE:
      continue
    d[v] = d[u] + 1
    colors[v] = Color.GRAY
    q.append(v+1)
  colors[u] = Color.BLACK

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

INF = 100100100

class Queue:
    __slots__ = ['Q', 'begin', 'end']
    def __init__(self):
        self.Q = [None] * 100
        self.begin = 0
        self.end = 0
    def full(self) -> bool:
        if self.begin == 0 and self.end == 99:
            return True
        elif self.begin == self.end + 1:
            return True
        else:
            return False
    def empty(self) -> bool:
        if self.begin == self.end:
            return True
        else:
            return False
    def insert(self, num: int):
        if self.full():
            print('Error: Queue is full.')
        else:
            if self.end == 99:
                self.end = 0
            else:
                self.end += 1
            self.Q[self.end-1] = num
    def pop(self) -> int:
        if self.empty():
            print('Error: Queue is empty.')
            return
        else:
            if self.begin == 99:
                self.begin = 0
                return self.Q[99]
            else:
                self.begin += 1
                return self.Q[self.begin-1]

def bfs(M: list, visited: list, d: list, v: int = 0):
    n = len(visited)
    Q = Queue()
    visited[v] = True
    d[v] = 0
    Q.insert(v)
    while not Q.empty():
        u = Q.pop()
        for i in range(n):
            if M[u][i] == 1 and not visited[i]:
                visited[i] = True
                d[i] = d[u] + 1
                Q.insert(i)


def main():
    n = int(input())
    M = [[0]*n for _ in range(n)]
    for _ in range(n):
        a = list(map(int, input().split()))
        i = a[0]-1
        for j in range(a[1]):
            k = a[j+2]-1
            M[i][k] = 1
    visited = [False] * n
    d = [INF] * n
    bfs(M, visited, d)
    for i, l in enumerate(d):
        if l == INF:
            print(i+1, -1)
        else:
            print(i+1, l)

if __name__ == '__main__': main()

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

Solution (Python):
N = int(input())
G = [None for i in range(N)]
for i in range(N):
    u, k, *vs = map(int, input().split())
    G[u-1] = [e-1 for e in vs]


from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

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

Solution (Python):



from collections import deque

n = int(input())
V = [[] for _ in range(n+1)]
for _ in range(n):
    inpt = list(map(int,input().split( )))
    if len(inpt)>2:
        V[inpt[0]] = inpt[2:]

lrg = 10000
D = [lrg]*(n+1)
End = [0]*(n+1)

D[1] = 0
Deq = deque()

time = 1
Q = [1]
Deq.append(1)

while len(Deq) > 0:
    v = Deq.popleft()
    for i in V[v]:
        D[i] = min(D[i],D[v]+1)
        if End[i] == 0:
            Deq.append(i)
        End[i] = 1


for i in range(1,n+1):
    if D[i]<lrg-1:
        print(i,D[i])
    else:
        print(i,-1)

Solution (Python):


from collections import Counter,deque


from sys import stdin,setrecursionlimit

setrecursionlimit(10**6)
input=stdin.readline

n=int(input().rstrip())
gragh=[[] for _ in range(n)]
q=deque()
for i in range(n):
    u=list(map(int,input().rstrip().split()))
    for j in u[2:]:
        gragh[u[0]-1].append(j-1)

dis=[-1]*n
dis[0]=0
q.append(0)
while len(q)!=0:
    v=q.popleft()
    for i in gragh[v]:
        if dis[i]!=-1:
            continue
        dis[i]=dis[v]+1
        q.append(i)
for i,j in enumerate(dis,1):
    print(i,j)

Solution (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()

Solution (Python):
from collections import deque
from typing import List
import sys


def bfs(adj_list: List[List[int]]) -> List[int]:
    n = len(adj_list)
    result: List[int] = [sys.maxsize for _ in range(n)]
    result[0] = 0
    queue: deque = deque()
    queue.append(0)

    while len(queue) > 0:
        cur = queue.popleft()
        for vertex in adj_list[cur]:
            if result[cur] + 1 < result[vertex]:
                result[vertex] = result[cur] + 1
                queue.append(vertex)

    return result


if __name__ == "__main__":
    num_vertices = int(input())
    adj_list: List[List[int]] = [[] for _ in range(num_vertices)]

    for _ in range(num_vertices):
        vertex, num_adjs, *adjs = map(lambda x: int(x), input().split())
        for i in range(num_adjs):
            adj_list[vertex - 1].append(adjs[i] - 1)

    result = bfs(adj_list)

    for i in range(num_vertices):
        if sys.maxsize == result[i]:
            result[i] = -1
        print(f"{i + 1} {result[i]}")

Solution (Python):
n=int(input())
e=[[] for _ in range(n)]
for _ in range(n):
    u,_,*v=map(lambda x:int(x)-1, input().split())
    e[u]=sorted(v)
q=[0]
d=[-1]*n
d[0]=0
while q:
    i=q.pop(0)
    for v in e[i]:
        if d[v]==-1:
            q.append(v)
            d[v]=d[i]+1
for i in range(n):
    print(i+1,d[i])

Solution (Python):
from collections import deque
q = deque([])
n = int(input())
G = []
for i in range(n):
  u, k, *vvv = list(map(int, input().split()))
  G.append([v-1 for v in vvv])
visited = [False for _ in range(n)]
q.append(0)
dist = [-1 for _ in range(n)]
dist[0] = 0
while q:
  u = q.popleft()
  visited[u] = True
  for v in G[u]:
    if visited[v] == True:
      continue
    else:
      q.append(v)
      visited[v] = True
      dist[v] = dist[u] + 1
    
for i in range(n):
  print(i+1, dist[i])

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

def main():
	n = int(input().strip())
	v = [[] for _ in range(n)]
	for i in range(n):
		v[i] = list(map(int, input().strip().split()))
	l = [-1] * (n+1)
	q = deque()
	q.append((1, 0))
	while len(q) != 0:
		id, d = q.popleft()
		
		if l[id] != -1:
			
			continue
		l[id] = d
		
		
		for i in range(v[id-1][1]):
			q.append((v[id-1][2+i], d+1))
			
				
				
	for i in range(1, n+1):
		print(i, l[i])

if __name__ == '__main__':
	main()

Solution (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)

Solution (Python):
from queue import Queue

n = int(input())
A = [[0 for i in range(n)] for j in range(n)]
d = [-1] * n

for i in range(n):
    u, k, *v = list(map(int, input().split()))
    for j in v:
        A[int(u)-1][int(j)-1] = 1

q = Queue()
q.put(0)
d[0] = 0

while not q.empty():

    u = q.get()

    for v in range(n):

        if A[u][v] == 1 and d[v] == -1:
            q.put(v)
            d[v] = d[u] + 1

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

Solution (Python):
from collections import deque

WHITE = 0
GRAY = 1
BLACK = 2

n = int(input())

M = [[0] * n for i in range(n)]

d = [-1] * (n)
color = [WHITE] * (n)


time = 0

def dfs_visit(u):
    global time
    time += 1
    color[u] = GRAY
    d[u] = time
    for v in range(n):
        if M[u][v] == 0:
            continue
        if color[v] == WHITE:
            dfs_visit(v)
    color[u] = BLACK
    time += 1

def bfs(s):
    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:
                continue
            d[v] = d[u] + 1
            queue.append(v)

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


if __name__ == "__main__":
    for i in range(n):
        arr = list(map(int, input().split()))
        for v in (arr[2:]):
            M[arr[0]-1][v-1] = 1

    bfs(0)

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

Solution (Python):
from collections import deque


INFINITY = 10 ** 10
WHITE = 0
GRAY = 1
BLACK = 2


def breadth_first_search(u_start = 0):
    color[u_start] = GRAY
    d[u_start] = 0
    que.append(u_start)

    while que:
        u = que.popleft()
        for v in range(n):
            if matrix[u][v] and color[v] == WHITE:
                color[v] = GRAY
                d[v] = d[u] + 1
                que.append(v)
        color[u] = BLACK



n = int(input())


matrix = [[0] * n for _ in range(n)]

for i in range(n):

    u, k, *V = map(int, input().split())

    for v in V:
        v -= 1
        matrix[i][v] = 1


color = [WHITE] * n
d = [INFINITY] * n
que = deque([])


breadth_first_search()



for i in range(n):
    if d[i] == INFINITY:
        distance = -1
    else:
        distance = d[i]

    print(i + 1, distance)

Solution (Python):
import collections
N = int(input())
P = [[0 for _ in range(N)] for _ in range(N)] 
for i in range(N):
    u,k,*varray = map(int,input().split()) 
    for v in varray:
        P[u-1][v-1] = 1    

D = [-1 for _ in range(N)]
D[0] = 0 
Q = collections.deque()
Q.append(0)
while len(Q) > 0:
    c = Q.popleft()
    for i in range(N):
        if P[c][i]==1 and D[i]==-1:
            D[i] = D[c]+1
            Q.append(i)
for v in range(N):
    print(v+1, D[v])

Solution (Python):
n = int(input())
al = [list(map(lambda x: int(x) - 1, input().split()))[2:] for _ in range(n)]
queue = [0]
d = [-1] * n
d[0] = 0
while len(queue) > 0:
    u = queue.pop(0)
    for v in al[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            queue.append(v)
for i, x in enumerate(d):
    print('{} {}'.format(i + 1, x))

Solution (Python):
import collections
n = int(input())
G = []
for i in range(n):
    T = [0]*n
    G.append(T)
for i in range(n):
    L = list(map(int,input().split()))
    for j in range(2,len(L)):
        G[i][L[j]-1] += 1
d = [float('inf')]*n
q = collections.deque()
q.append(0)
d[0] = 0
while len(q) > 0:
    start = q.popleft()
    for i in range(n):
        if G[start][i] == 1:
            if d[i] == float('inf'):
                q.append(i)
                d[i] = d[start]+1
for i in range(n):
    if d[i] != float('inf'):
        print(i+1,d[i])
    else:
        print(i+1,-1)

Solution (Python):
n=int(input())
ne=[[] for _ in range(n+1)]
for _ in range(n):
    u,k,*v=map(int,input().split())
    ne[u]=v
dis=[-1]*(n+1)
dis[1]=0
q=[1]
while q:
    p=q.pop(0)
    for e in ne[p]:
        if dis[e]==-1:
            dis[e]=dis[p]+1
            q.append(e)
for i in range(1,n+1):
    print(i,dis[i])

Solution (Python):
import collections
n=int(input())
l=[]
for i in range(n):
  l1=list(map(int,input().split()))
  l2=[]
  if l1[1]==0:
    l2=["0" for j in range(n)]
  else:
    for j in range(n):
      if j+1 in l1[2:]:
        l2.append("1")
      else:
        l2.append("0")
  l.append(l2)
D=[-1 for i in range(n)]
D[0]=0
q=collections.deque()
q.append(0)
while len(q)!=0:
  cur=q.popleft()
  for d in range(n):
    if l[cur][d]=="1" and D[d]==-1:
      D[d]=D[cur]+1
      q.append(d)
for i in range(n):
  print(i+1,D[i])

Solution (Python):
n=int(input())
d=[0]+[float('inf')]*(n-1)

v=[[]]*n
for i in range(n):
    tmp=list(map(int,input().split()))
    tmp=[i-1 for i in tmp[2:]]
    v[i]=tmp

que=[0]
while que!=[]:
    m=que.pop(0)
    for i in v[m]:
        if d[i]==float('inf'):
            que.append(i)
            d[i]=d[m]+1
for i in range(n):
    if d[i]==float('inf'):
        d[i]=-1
    print(i+1,d[i])

Solution (Python):
import queue

n = int(input())

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

for i in range(n):
    _, _, *adj[i] = list(map(int, input().split()))

q = queue.Queue()

d = [-1] * n
flag = [0] * n

q.put(1)
d[0] = 0
flag[0] = 1

while not q.empty():
    u = q.get()

    for v in adj[u-1]:
        if flag[v-1] == 0:
            flag[v-1] = 1
            d[v-1] = d[u-1] + 1
            q.put(v)

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

Solution (Python):

import sys
import collections
INF = 10000000
queue = collections.deque()  
n = int(input())
graph = [[0] * (n+1) for _ in range(n+1)]
yet = [i for i in range(1, n+1)]
ans = [-1] * (n+1)
for i in range(1, n+1):
    tmp = [int(ele) for ele in input().split()]
    for adjc in tmp[2:]:
        graph[i][adjc] = 1

d = [INF] * (n+1)
d[1] = 0


def main():
    global queue, d
    queue.appendleft(1)
    bfs(queue)
    d = list(map(lambda x: -1 if x == INF else x, d))
    for i in range(1, n+1):
        print(str(i) + " " + str(d[i]))


def bfs(queue):
    global graph, yet
    if len(queue) == 0:
        return

    n = queue[-1]
    yet.remove(n)

    
    for i, adjacency in enumerate(graph[n]):
        if adjacency == 1 and i in yet and i not in queue:  
            queue.appendleft(i)
            
            d[i] = min(d[i], d[n] + 1)
    else:
        queue.pop()
        bfs(queue)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque


def bfs(s):
    flag_list[s] = 1
    d_list[s] = 0
    q.append(s)
    while len(q)>0:
        u = q.popleft()
        for v in range(n):
            if m_list[u][v] == 1 and flag_list[v] == 0:
                flag_list[v] = 1
                d_list[v] = d_list[u] + 1
                q.append(v)
        flag_list[u] = 2


if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    m_list = [[0]*n for _ in range(n)]
    d_list = [-1]*n
    flag_list = [0]*n 
    q = deque([])
    for _ in range(n):
        input_list = list(map(int, input().split()))
        index = input_list[0] - 1
        if input_list[1] > 0:
            for a in input_list[2:]:
                m_list[index][a-1] = 1
    bfs(0)
    for i, d in enumerate(d_list):
        print(i+1, d_list[i])

Solution (Python):
from collections import deque


n = int(input())
g_list = {}
for _ in range(n):
    n1, num, *cl = map(int, input().split())
    g_list[n1] = cl


GRAY = 1
WHITE = 0
BLACK = 2


class Graph():
    def __init__(self, g_list):
        self.g_list = g_list
        self.dst = [-1] * (len(g_list)+1)
        self.stack = deque([])
        self.colors = [WHITE] * (len(g_list)+1)

    def bfs(self, s):
        self.colors[s] = GRAY
        self.dst[s] = 0
        self.stack.append(s)

        while self.stack:
            u = self.stack.popleft()
            for v in self.g_list[u]:
                if self.colors[v] == WHITE:
                    self.colors[v] = GRAY
                    self.dst[v] = self.dst[u] + 1
                    self.stack.append(v)
            self.colors[u] = BLACK


g = Graph(g_list)
g.bfs(1)
for i in range(1, n+1):
    print(i, g.dst[i])

Solution (Python):

"""
Created on Sat Apr  6 11:50:13 2019

@author: Yamazaki Kenichi
"""
from collections import deque

n = int(input())
A = [[]] + [list(map(int,input().split())) for i in range(n)]






T = [[-1, -1] for i in range(n+1)]
T[1][0], T[1][1] = 1, 0
q = deque([1])
def dfs():
    global depth
    while len(q) > 0:
        for i in range(A[q[0]][1]):
            if T[A[q[0]][i+2]][0] == -1:
                q.append(A[q[0]][i+2])
                T[q[-1]][0] = 1
                T[q[-1]][1] = T[q[0]][1] + 1
        q.popleft()
dfs()
for i in range(1,n+1):
    print(i,T[i][1])

Solution (Python):
n = int(input())
g = [[0]*(n+1) for _ in range(n+1)]
for i in range(n):
    u, k, *v, = map(int, input().split())
    for vi in v:
        g[u][vi] = 1

d = [-1]*(n+1)
d[1] = 0

l = [1]
while len(l) > 0:
    u = l.pop(0)
    for i, v in enumerate(g[u]):
        if v == 1 and d[i] < 0:
            d[i] = d[u]+1
            l.append(i)

for i in range(1, n+1):
    print(f"{i} {d[i]}")

Solution (Python):
n = int(input())
adj = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    l = list(map(int, input().split()))
    if l[1] == 0:
        continue 
    else:
        for j in range(2,len(l)):
            adj[l[0]-1][l[j]-1] = 1

color = ['white' for _ in range(n)]
d = [-1 for _ in range(n)]
color[0] = 'grey'
d[0] = 0
Q = [1]
while Q:
    u = Q.pop(0)
    color[u-1] = 'black'
    for v in range(1, n+1):
        if adj[u-1][v-1] == 1 and color[v-1] == 'white':
            Q.append(v)
            color[v-1] = 'grey'
            d[v-1] = d[u-1] + 1  

for i in range(n):
    print(' '.join([str(i+1), str(d[i])]))

Solution (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)

Solution (Python):

import queue

q = queue.Queue()
A = [[]*101 for _ in range(101)]
d = [-1]*101
visited = [False]*101

n = int(input().rstrip())
for i in range(n):
    line = [int(j) for j in input().rstrip().split()]
    A[i+1].extend(line[2:])

d[1] = 0

q.put(1)
while not q.empty():
    v = q.get()
    if visited[v] == True:
        continue
    visited[v] = True
    for i in A[v]:
        if d[i] == -1:
            d[i] = d[v] + 1
        else:
            d[i] = min(d[i],d[v] + 1)
        q.put(i)
        
for i in range(n):
    print(str(i+1)+" "+str(d[i+1]))

Solution (Python):
import sys
import queue
readline = sys.stdin.readline
write = sys.stdout.write

n = int(input())
G = [None for i in range(n+1)]
dist = [-1,]*(n+1)
for i in range(n):
    node_id, k, *adj = map(int, readline().split())
    
    G[node_id] = adj

def bfs(G):
    
        
        
        
        
    cnt = -1

    q1 = queue.Queue()
    q2 = queue.Queue()
    q1.put(1)
    while not q1.empty():
        cnt += 1
        while not q1.empty():
            val = q1.get()
            if dist[val] != -1:
                continue
            dist[val] = cnt
            listlen = len(G[val])
            for i in range(listlen):
                q2.put(G[val][i])
        while not q2.empty():
            q1.put(q2.get())
bfs(G)
for i in range(1, n+1):
    write(str(i) + " " + str(dist[i]) + "\n")

Solution (Python):

v = int(input())
vlist = [0]*v
for num in range(v):
    temp = list(map(int,input().split()))
    if temp[1] != 0:
        vlist[num] = temp[2:]
deep = [0]+[-1]*(v-1)
waiting = [1]

while waiting:
    vertex = waiting.pop(0)
    if vlist[vertex-1]:
        for subv in vlist[vertex-1]:
            if deep[subv-1] == -1:
                deep[subv-1] = deep[vertex-1]+1
                waiting += [subv]

count = 0
for num in deep:
    count += 1
    print(count,num)