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

"""
Created on Sun Jul  8 10:56:33 2018

@author: maezawa
"""
n = int(input())
adj = [[] for _ in range(n)]
d = [-1 for _ in range(n)]
d[0] = 0


for j in range(n):
    ain = list(map(int, input().split()))
    u = ain[0]
    k = ain[1]
    for i in range(k):
        adj[u-1].append(ain[i+2]-1)
    adj[u-1].sort()
    

stack = [0]

while stack:
    
    current = stack[-1]
    flag = 0
    for k in adj[current]:
        if d[k] < 0:
            d[k] = d[current]+1
            stack.append(k)
            flag = 1
        elif d[k] > d[current]+1:
            d[k] = d[current]+1
            stack.append(k)
            flag = 1
    if flag == 0:
        stack.pop()

    
    

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

Solution (Python):

from collections import deque


class Graph:
    def __init__(self, n, adj_matrix):
        self.n = n
        self.adj_matrix = adj_matrix

    def show(self):
        for _ in self.adj_matrix:
            print(*_)

    def dfs(self):
        self.states = [2] * self.n
        self.d = [None] * self.n
        self.f = [None] * self.n
        self.time = 0

        for u in range(self.n):
            if self.states[u] == 2:
                self.dfs_visit(u)

    def dfs_visit(self, u):
        self.states[u] = 1
        self.time += 1
        self.d[u] = self.time

        for v, edge in [(v, edge) for v, edge in enumerate(self.adj_matrix[u])
                        if edge]:
            if self.states[v] == 2:
                self.dfs_visit(v)

        self.states[u] = 0
        self.time += 1
        self.f[u] = self.time

    def show_dfs(self, start=0):
        self.dfs()
        for i, (d, f) in enumerate(zip(self.d, self.f)):
            print(i + 1, d, f)

    def bfs(self, start):
        self.states = [0] * self.n
        self.dists = [float('inf')] * self.n

        queue = deque([start])
        self.dists[start] = 0
        while queue:
            u = queue.popleft()
            edges = self.adj_matrix[u]

            for v, edge in [(v, edge) for v, edge in enumerate(edges) if edge]:
                if self.states[v]:
                    continue

                if self.dists[v] > self.dists[u] + 1:
                    self.dists[v] = self.dists[u] + 1
                queue.append(v)

                self.states[v] = 1

        self.dists = [
            -1 if dist == float('inf') else dist for dist in self.dists
        ]

    def show_bfs(self, start=0):
        self.bfs(start=start)
        for i, dist in enumerate(self.dists):
            print(i + 1, dist)


if __name__ == '__main__':
    n = int(input())
    adj_matrix = [[0] * n for i in range(n)]
    for i in range(n):
        for v in input().split()[2:]:
            adj_matrix[i][int(v) - 1] = 1

    g = Graph(n, adj_matrix)
    g.show_bfs()

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

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

Solution (Python):
from collections import deque
n = int(input())
A = [0]*(n+1)
D = [-1]*(n+1)
DP = [0]*(n+1)
d = deque()
for i in range(n):
    A[i+1] = [int(i) for i in input().split()]
d.append(1)
D[1] = 0
DP[1] = 1
while(len(d)>0):
    tmp = d.pop()
    for i in A[tmp][2:]:
        if not DP[i]:
            D[i] = D[tmp]+1
            DP[i] = 1
            d.appendleft(i)
for i in range(1,n+1):
    tmp = "{} {}".format(i,D[i])
    print(tmp)

Solution (Python):

inf = 100000000
n = int(input())

List = [0] + [list(map(int,input().split())) for i in range(n)]
d = [inf for i in range(n+1)]
color = ["white" for i in range(n+1)]

s = 1
Q = [s]
d[s] = 0
color[s] = "gray"

while Q != []:
    q = Q.pop(0)
    k = List[q][1]
    for i in List[q][2:2+k]:
        if color[i] == "white":
            Q.append(i)
        d[i] = min(d[q] + 1, d[i])
    color[q] = "gray"


for i, dis in enumerate(d[1:], 1):
    if dis == inf:
        dis = -1
    print(i, dis)

Solution (Python):
def get_depth(graph,tmp_depth,vertex_list,depth_list):
    new_vertex_list=[]
    for vertex in vertex_list:
        for j in range(len(depth_list)):
            if(graph[vertex][j]!=0 and depth_list[j]==-1):
                depth_list[j]=tmp_depth + 1
                new_vertex_list.append(j)
    if(len(new_vertex_list)!=0):
        get_depth(graph,tmp_depth+1,new_vertex_list,depth_list)



n=int(input())
graph=[[0]*n for loop in range(n)]
for loop in range(n):
    tmp_ope=list(map(int,input().split()))
    for j in range(tmp_ope[1]):
        graph[tmp_ope[0]-1][tmp_ope[j+2]-1]=1


depth_list=[-1]*n
depth_list[0]=0
vertex_list=[0]
get_depth(graph,0,vertex_list,depth_list)

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

Solution (Python):
from collections import deque

n = int(input())

adj = [0]*n 
d = [-1]*n 
c = ['w']*n 


for i in range(n):
    tmp = list(map( int, input().split() ) )
    adj[tmp[0]-1] = list(map(lambda x : x - 1, tmp[2:]))


s = 0
d[s] = 0
c[s] = 'g'


Q = deque()
Q.append(s)

while Q:
    u = Q.popleft()
    for v in adj[u]:
        if c[v] == 'w':
            c[v] = 'g'
            d[v] = d[u] + 1
            Q.append(v)
    c[u] = 'b'
    

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

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

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

Solution (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.append(i)
    

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

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

Solution (Python):
N= int(input())
E = [input().split()[2:] for _ in range(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.append(i)
    

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Solution (Python):
from queue import Queue

n = int(input())
A = [[0 for i in range(n)] for j in range(n)]
d = [-1 for i in range(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):


import sys
from collections import deque

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

N=INT()
nodes=[[] for i in range(N)]
for i in range(N):
    l=LIST()
    u=l[0]
    l=l[2:]
    for v in l:
        nodes[u-1].append(v-1)
    nodes[u-1].sort()

que=deque()
que.append((0, 0))
costs=[-1]*N
while len(que):
    cost,node=que.popleft()
    if costs[node]==-1:
        costs[node]=cost
        for v in nodes[node]:
            que.append((cost+1, v))

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

Solution (Python):
from collections import deque

n = int(input())
points = [0 for i in range(n)]

class Point:
    def __init__(self, number, arrow):
        self.number = number        
        self.arrow = arrow
        self.destination = []
        self.distance = -1
        self.hadSearched = False

for i in range(n):
    L = list(map(int, input().split()))
    points[i] = Point(i+1, L[1])
    if L[1] >= 1:
        points[i].destination = L[2:]

def bfs(coord):
    dq = deque()
    coord.hadSearched = True
    dq.appendleft((0, coord))

    while dq:
        steps, po = dq.pop()
        po.distance = steps

        if len(po.destination) > 0:
            for des in po.destination:
                if points[int(des)-1].hadSearched == False:
                    points[int(des)-1].hadSearched = True
                    dq.appendleft((steps+1, points[int(des)-1]))

bfs(points[0])

for i in range(n):
    print("{} {}".format(i+1, points[i].distance))

Solution (Python):
n = int(input())
G = [[] for _ in range(n)]
for _ in range(n):
    u, k, *v = [int(i) for i in input().split()]
    G[u - 1] = v
NIL = 100
Q = [[1, 0]]
F = []
D = [NIL for _ in range(n)]
while Q != []:
    u, d = Q.pop(0)
    if d < D[u-1]:
        D[u-1] = d
    if u not in F:
        F.append(u)
    for v in G[u-1]:
        if v not in F:
            Q.append([v, d+1])
'''
for ni in range(1, n):
    Q = [[ni+1, 0]]
    F = []
    while Q != []:
        u, d = Q.pop(0)
        if u == 1 and d < D[ni]:
            D[ni] = d
        if u not in F:
            F.append(u)
        for v in G[u-1]:
            if v not in F:
                Q.append([v, d+1])
'''
for ni in range(n):
    if D[ni] == NIL:
        print(ni+1, -1)
    else:
        print(ni+1, D[ni])

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

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

d = [-1] * n

s = 1
q = []
d[s - 1] = 0
q.append(s)
while len(q):
    u = q.pop()
    v = adj[u - 1]
    for vi in v:
        if d[vi - 1] == -1:
            d[vi - 1] = d[u - 1] + 1         
            q.append(vi)
        elif d[vi - 1] > d[u - 1] + 1:
            d[vi - 1] = d[u - 1] + 1            
            q.append(vi)

for i, di in enumerate(d):
    print(i + 1, di)

Solution (Python):
from sys import stdin

X = [ 0 for i in range(100) ]
d = [ 0 for i in range(100) ]
G = [[ 0 for i in range(100) ] for i in range(100)]
queue = [ 0 for i in range(100) ]

t = 0
head = 0
tail = 0

def BFS(i) :
	global head
	for j in range(n) :
		if G[i][j] == 1 and d[j] == -1 :
			d[j] = d[i] + 1
			queue[head] = j
			head += 1

def tailQ() :
	global tail
	tail += 1
	return queue[tail-1]


n = int(input())
for i in range(n) :
	X[i] = stdin.readline().strip().split()


for i in range(n) :
	for j in range(int(X[i][1])) :
		G[int(X[i][0])-1][int(X[i][j+2])-1] = 1
	if i != 0 : d[i] = -1

BFS(0)
while head-tail != 0 : 
	BFS(tailQ())

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

Solution (Python):



import sys

class Graph(object):
    def __init__(self, size):
        super(Graph, self).__init__()
        self.__size = size
        self.__vertices = [None] * size

    def add_vertex(self, vertex):
        self.__vertices[vertex.id_ - 1] = vertex

    def get_vertex(self, vid):
        return self.__vertices[vid - 1]

    def breadth_first_search(self):
        ds = [-1] * self.__size
        vs = [None] * self.__size
        vs[0] = [self.get_vertex(1)]
        ds[0] = 0
        vs_idx = 0
        while vs_idx < self.__size and vs[vs_idx] != None:
            vlst = vs[vs_idx]
            vs_idx += 1
            for vtx in vlst:
                for advid in vtx.adjacents:
                    adv = self.get_vertex(advid)
                    if ds[advid - 1] == -1:
                        ds[advid - 1] = vs_idx
                        if vs[vs_idx] == None:
                            vs[vs_idx] = []
                        vs[vs_idx].append(adv)
        for idx, d in enumerate(ds):
            print '%d %d' % ((idx + 1), d)

    def __str__(self):
        str_ = ''
        for e in self.__vertices:
            str_ += '%s\n' % e
        return str_

class Vertex(object):
    def __init__(self, id_):
        super(Vertex, self).__init__()
        self.id_ = id_
        self.adjacents = []
        self.next_idx = 0

    def add_adjacent(self, avid):
        self.adjacents.append(avid)

    def __str__(self):
        str_ = '%d ' % self.id_
        if len(self.adjacents) == 0:
            str_ += '0'
        else:
            str_ += '%d' % len(self.adjacents)
            for e in self.adjacents:
                str_ += ' %d' % e
        return str_



s = int(sys.stdin.readline().strip())
graph = Graph(s)
for _ in range(0, s):
    vals = [int(x) for x in sys.stdin.readline().strip().split(' ')]
    v = Vertex(vals[0])
    graph.add_vertex(v)
    if vals[1] == 0: continue
    for i in range(0, vals[1]):
        v.add_adjacent(vals[2 + i])

graph.breadth_first_search()

Solution (Python):



import sys


def bfs(matrix):
    distances = [-1 for _ in range(len(matrix))]
    queue = [0]
    distances[0] = 0

    while 0 < len(queue):
        node_id = queue.pop(0)  
        distance = distances[node_id]
        for index, candidate in enumerate(matrix[node_id]):
            if candidate == 1 and distances[index] == -1:
                
                queue.append(index)
                distances[index] = distance + 1

    return distances

if __name__ == "__main__":
    
    
    
    
    
    
    
    
    lines = sys.stdin.readlines()
    dimension = int(lines[0])
    matrix = [[0 for _ in range(dimension)] for _ in range(dimension)]

    
    for index, line in enumerate(lines[1:]):
        for edge in [int(x) for x in line.strip().split(" ")[2:]]:
            matrix[index][edge - 1] = 1

    distances = bfs(matrix)
    for index, distance in enumerate(distances):
        print("%d %d" % (index + 1, distance))

Solution (Python):
n = int(raw_input())



graph = [[] for i in range(n)]
for i in range(n):
    entry = map(int,raw_input().strip().split(' '))
    u = entry[0]-1
    for v in entry[2:]:
        v -= 1
        graph[u].append(v)

d = [-1 for i in range(n)]
d[0] = 0
t = 1
q = []
q.append(0)
while len(q) > 0:
    u = q[0]
    for v in graph[u]:
        if d[v] == -1:
            q.append(v)
            d[v] = d[u]+1
    del q[0]

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

Solution (Python):


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

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

Solution (Python):
n = int(raw_input())
G = [[0 for i in range(n+1)] for j in range(n+1)]
d = [-1 for i in range(n+1)]

for i in range(n):
    v = map(int, raw_input().split())
    for j in range(v[1]):
        G[v[0]][v[2+j]] = 1

flag = [0 for i in range(n+1)]
tn = [[0 for i in range(n+1)] for j in range(n+1)]
tn[0][1] = 1
r = 0
for i in range(n):
    for j in range(1, n+1):
        if flag[j] == 0 and tn[i][j] == 1:
            flag[j] = 1
            d[j] = r
            for k in range(1, n+1):
                if G[j][k] == 1:
                    tn[i+1][k] = 1
    r += 1

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

Solution (Python):
class node:
    def __init__(self, num):
        self.number     = num
        self.distance   = -1
        self.link_node  = []
        self.is_serched = False

class queue:
    def __init__(self):
        self.top = 0
        self.bottom = 0
        self.que = []
    
    def dequeue(self):
        self.top = self.top + 1
        return self.que[self.top - 1]
    
    def enqueue(self, item):
        self.que.append(item)
        self.bottom = self.bottom + 1
    
    def is_empty(self):
        if self.top == self.bottom:
            return True
        else:
            return False

n = input()
node_list = [None] * (n + 1)

for i in xrange(1, n + 1):
    node_list[i] = node(i)

for i in xrange(1, n + 1):
    line = raw_input().split()
    for node_num in line[2 : ]:
        node_list[i].link_node.append(node_list[int(node_num)])

node_que = queue()

node_list[1].distance = 0
node_que.enqueue(node_list[1])
while node_que.is_empty() == False:
    top_item = node_que.que[node_que.top]
    top_item.is_serched = True
    for item in top_item.link_node:
        if item.is_serched == False:
            node_que.enqueue(item)
            if item.distance == -1:
                item.distance = top_item.distance + 1
            elif item.distance > top_item.distance + 1:
                item.distance = top_item.distance + 1
    node_que.dequeue()

for item in node_list[1 : ]:
    print '%s %s' % (str(item.number), str(item.distance))

Solution (Python):

def BFS(s = 0):
    Q.pop(0)
    color[s] = 2
    for j in range(len(color)):
        if A[s][j] == 1 and color[j] == 0:
            Q.append(j)
            color[j] = 1
            d[j] = d[s] + 1
    if len(Q) != 0:
        BFS(Q[0])

n = int(raw_input())
A = [0] * n
for i in range(n):
    A[i] = [0] * n

for i in range(n):
    value = map(int, raw_input().split())
    u = value[0] - 1
    k = value[1]
    nodes = value[2:]
    for j in range(k):
        v = nodes[j] - 1
        A[u][v] = 1

color = [0] * n
Q = [0]
d = [-1] * n
d[0] = 0

BFS(0)

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

Solution (Python):
n = int(raw_input())
 
d = [99999 for i in range(n)]
G = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
 
def BFS(s):
    for e in range(n):
        if M[s][e] == 1:
            if d[e] > d[s] + 1:
                d[e] = d[s]+1
                BFS(e)
 
for i in range(n):
    G = map(int, raw_input().split())
    for j in range(G[1]):
        M[G[0]-1][G[2+j]-1] = 1
 
d[0] = 0
for s in range(n):
        BFS(s)
for s in range(n):
    if d[s] == 99999:
        d[s] = -1
for s in range(n):
    print'{0} {1}'.format(s+1, d[s])

Solution (Python):

from __future__ import division, print_function
from sys import stdin
from Queue import Queue
 
 
def main():
    num = int(stdin.readline())
 
    L = []
    for _ in xrange(num):
        L.append([int(s) for s in stdin.readline().split()[2:]])
 
    d = [-1] * num
    d[0] = 0
    q = Queue(100)
    q.put(0)
    while not q.empty():
        u = q.get()
        for v in L[u]:
            if d[v-1] < 0:
                d[v-1] = d[u] + 1
                q.put(v-1)
 
    for i, v in enumerate(d):
        print(i+1, v)
 
 
main()

Solution (Python):
from collections import deque

n = int(input())
g = [None] * n
visited = [0] * n
dist = [-1] * n
queue = deque()

while n:
    l = list(map(int, input().split()))
    connected = [i - 1 for i in l[2:]]
    g[l[0] - 1] = [i - 1 for i in l[2:]]
    n -= 1

queue.append((0, 0))
visited[0] = 1

while queue:
    i, d = queue.popleft()
    dist[i] = d
    for c in g[i]:
        if not visited[c]:
            visited[c] = 1
            queue.append((c, d + 1))

for i, d in enumerate(dist):
    print(i + 1, d)

Solution (Python):
n = int(raw_input())
  
d = [99999 for i in range(n)]
G = [0 for i in range(n)]
v = [[0 for i in range(n)] for j in range(n)]
  
def BFS(s):
  for e in range(n):
    if v[s][e] == 1:
      if d[e] > d[s] + 1:
        d[e] = d[s]+1
        BFS(e)
  
for i in range(n):
  G = map(int, raw_input().split())
  for j in range(G[1]):
    v[G[0]-1][G[2+j]-1] = 1
  
d[0] = 0
for s in range(n):
  BFS(s)
for s in range(n):
  if d[s] == 99999:
    d[s] = -1
for s in range(n):
  print'{0} {1}'.format(s+1, d[s])

Solution (Python):
n = int(raw_input())
   
d = [99999 for i in range(n)]
G = [0 for i in range(n)]
v = [[0 for i in range(n)] for j in range(n)]
   
def BFS(s):
  for e in range(n):
    if v[s][e] == 1:
      if d[e] > d[s] + 1:
        d[e] = d[s]+1
        BFS(e)
   
for i in range(n):
  G = map(int, raw_input().split())
  for j in range(G[1]):
    v[G[0]-1][G[2+j]-1] = 1
   
d[0] = 0
for s in range(n):
  BFS(s)
for s in range(n):
  if d[s] == 99999:
    d[s] = -1
for s in range(n):
  print'{0} {1}'.format(s+1, d[s])

Solution (Python):
n = int(raw_input())
   
d = [99999 for i in range(n)]
G = [0 for i in range(n)]
v = [[0 for i in range(n)] for j in range(n)]
   
def BFS(s):
  for e in range(n):
    if v[s][e] == 1:
      if d[e] > d[s] + 1:
        d[e] = d[s]+1
        BFS(e)
   
for i in range(n):
  G = map(int, raw_input().split())
  for j in range(G[1]):
    v[G[0]-1][G[2+j]-1] = 1
   
d[0] = 0
for s in range(n):
  BFS(s)
for s in range(n):
  if d[s] == 99999:
    d[s] = -1
for s in range(n):
  print'{0} {1}'.format(s+1, d[s])

Solution (Python):
n = int(raw_input())
   
dis = [99999 for i in range(n)]
G = [0 for i in range(n)]
v = [[0 for i in range(n)] for j in range(n)]
   
def BFS(s):
  for e in range(n):
    if v[s][e] == 1:
      if dis[e] > dis[s] + 1:
        dis[e] = dis[s]+1
        BFS(e)
   
for i in range(n):
  G = map(int, raw_input().split())
  for j in range(G[1]):
    v[G[0]-1][G[2+j]-1] = 1
   
dis[0] = 0
for s in range(n):
  BFS(s)
for s in range(n):
  if dis[s] == 99999:
    dis[s] = -1
for s in range(n):
  print'{0} {1}'.format(s+1, dis[s])

Solution (Python):


n = int(raw_input())
  
d = [99999 for i in range(n)]
G = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
  
def BFS(s):
    for e in range(n):
        if M[s][e] == 1:
            if d[e] > d[s] + 1:
                d[e] = d[s]+1
                BFS(e)
  
for i in range(n):
    G = map(int, raw_input().split())
    for j in range(G[1]):
        M[G[0]-1][G[2+j]-1] = 1
  
d[0] = 0
for s in range(n):
        BFS(s)
for s in range(n):
    if d[s] == 99999:
        d[s] = -1
for s in range(n):
    print'{0} {1}'.format(s+1, d[s])

Solution (Python):
n = int(raw_input())
d = [100 for i in range(n)]
G = [0 for i in range(n)]
v = [[0 for i in range(n)] for j in range(n)]

def BFS(s):
	for e in range(n):
		if v[s][e] == 1:
			if d[e] > d[s] + 1:
				d[e] = d[s]+1
				BFS(e)

for i in range(n):
	G = map(int, raw_input().split())
	for j in range(G[1]):
		v[G[0]-1][G[j+2]-1] = 1
d[0] = 0

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

Solution (Python):
n = input()

d = [-1 for i in xrange(n + 1)]
Q = []

color = ['WHITE' for i in xrange(n + 1)]

graph_map = [[0 for j in xrange(n + 1)] for i in xrange(n + 1)]

for i in xrange(1, n + 1):
    tmp = map(int, raw_input().split())
    for j in xrange(tmp[1]):
        graph_map[i][tmp[j + 2]] = 1

color[1] = 'GRAY'
d[1] = 0
Q.append(1)

while len(Q) != 0:
    u = Q.pop(0)
    for v in xrange(1, n + 1):
        if graph_map[u][v] == 1 and color[v] == 'WHITE':
            color[v] = 'GRAY'
            d[v] = d[u] + 1
            Q.append(v)
    color[u] = 'BLACK'

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

Solution (Python):
n = int(raw_input())
d = [100 for i in range(n)]
G = [0 for i in range(n)]
v = [[0 for i in range(n)] for j in range(n)]
 
def Bread(s):
    for e in range(n):
        if v[s][e] == 1:
            if d[e] > d[s] + 1:
                d[e] = d[s]+1
                Bread(e)
 
for i in range(n):
    G = map(int, raw_input().split())

    for j in range(G[1]):
        v[G[0]-1][G[j+2]-1] = 1

d[0] = 0
 
for i in range(n):
    Bread(i)

for i in range(n):
    if d[i] == 100:
        d[i] = -1

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

Solution (Python):
from __future__ import print_function
import time
from sys import stdin
from Queue import Queue
start = time.clock()
i = 0
num=int(stdin.readline())
L=[]
for _ in range(num):
    L.append([int(s) for s in stdin.readline().split()[2:]])
 
d=[-1]*num
d[0]=0
q=Queue(100)
q.put(0)
while not q.empty():
    u=q.get()
    for v in L[u]:
        if d[v-1]<0:
            d[v-1]=d[u]+1
            q.put(v-1)
for i,v in enumerate(d):
    print (i+1,v)

Solution (Python):
n = int(raw_input())
d = [100 for i in range(n)]
G = [0 for i in range(n)]
v = [[0 for i in range(n)] for j in range(n)]
  
def Bread(s):
    for e in range(n):
        if v[s][e] == 1:
            if d[e] > d[s] + 1:
                d[e] = d[s]+1
                Bread(e)
  
for i in range(n):
    G = map(int, raw_input().split())
 
    for j in range(G[1]):
        v[G[0]-1][G[j+2]-1] = 1
 
d[0] = 0
  
for i in range(n):
    Bread(i)
 
for i in range(n):
    if d[i] == 100:
        d[i] = -1
 
for i in range(n):
    print i+1, d[i]

Solution (Python):
n = int( raw_input() )
d = [ 100 for i in range(n) ]
G = [ 0 for i in range(n) ]
v = [ [ 0 for i in range(n) ] for j in range(n) ]
  
def BFS(s):
    for e in range(n):
        if v[ s ][ e ] == 1:
            if d[ e ] > d[ s ] + 1:
                d[ e ] = d[ s ] + 1
                BFS(e)
  
for i in range(n):
    G = map( int , raw_input().split() )
 
    for j in range( G[1] ):
        v[ G[0] -1 ][ G[ 2+j ] -1 ] = 1
 
d[0] = 0
  
for i in range(n):
    BFS(i)
 
for i in range(n):
    if d[ i ] == 100:
        d[ i ] = -1
 
for i in range(n):
    print i+1 , d[ i ]

Solution (Python):
n = input()
  
d = [-1 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
color = [0 for i in range(n)]
  
def BFS(s):
  color[0] = 1
  q = []
  q.append(s)
  d[s] = 0
  while len(q) != 0:
    u = q[0]
    q.pop(0)
    for v in range(n):
      if M[u][v] == 1 and color[v] == 0:
        color[v] = 1
        d[v] = d[u] + 1
        q.append(v)
  color[u] = 2
  for i in range(n):
    print i+1, d[i]
  
for i in range(n):
  G = map(int, raw_input().split())
  for j in range(G[1]):
    M[G[0]-1][G[2+j]-1] = 1
  
BFS(0)

Solution (Python):

n = input()
d = [99999 for i in range(n)]
G = [0 for i in range(n)]
v = [[0 for i in range(n)] for j in range(n)]
   
def bfs(u):
  for i in range(n):
    if v[u][i] == 1:
      if d[i] > d[u] + 1:
         d[i] = d[u] + 1
         bfs(i)
    else:
      continue        
def _(): 
 d[0] = 0
 for i in range(n):
   bfs(i)
 for i in range(n):
   if d[i] == 99999:
      d[i] = -1
 for i in range(n):
   print '{0} {1}'.format(i+1, d[i])


for i in range(n):
  G = map(int, raw_input().split())
  for j in range(G[1]):
    v[G[0]-1][G[2+j]-1] = 1

_()

Solution (Python):
n = int(raw_input())
    
d = [99999 for i in range(n)]
G = [0 for i in range(n)]
v = [[0 for i in range(n)] for j in range(n)]
    
def BFS(s):
  for e in range(n):
    if v[s][e] == 1:
      if d[e] > d[s] + 1:
        d[e] = d[s]+1
        BFS(e)
    
for i in range(n):
  G = map(int, raw_input().split())
  for j in range(G[1]):
    v[G[0]-1][G[2+j]-1] = 1
    
d[0] = 0
for s in range(n):
  BFS(s)
for s in range(n):
  if d[s] == 99999:
    d[s] = -1
for s in range(n):
  print'%d %d' %(s+1, d[s])

Solution (Python):

from __future__ import division, print_function
from sys import stdin
from Queue import Queue
 
 
def main():
    num = int(stdin.readline())
 
    L = []
    for _ in xrange(num):
        L.append([int(s) for s in stdin.readline().split()[2:]])
 
    d = [-1] * num
    d[0] = 0
    q = Queue(100)
    q.put(0)
    while not q.empty():
        u = q.get()
        for v in L[u]:
            if d[v-1] < 0:
                d[v-1] = d[u] + 1
                q.put(v-1)
 
    for i, v in enumerate(d):
        print(i+1, v)
 
 
main()