Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

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.



Sample input:
4
1 2 2 4
2 1 4
3 0
4 1 3


Sample output:
1 0
2 1
3 2
4 1

Submission status: Time Limit Exceeded

Solution code:
import abc


class AdjacentGraph:
    """Implementation adjacency-list Graph.
    Beware ids are between 1 and size.
    """
    def __init__(self, size):
        self.size = size
        self._nodes = [[0] * (size+1) for _ in range(size+1)]

    def set_adj_node(self, id_, adj_id):
        self._nodes[id_][adj_id] = 1

    def __iter__(self):
        self._id = 0
        return self

    def __next__(self):
        if self._id < self.size:
            self._id += 1
            return (self._id, self._nodes[self._id][1:])

        raise StopIteration()

    def dfs(self, handler=None):
        def find_first():
            try:
                return visited.index(0)
            except ValueError:
                return None

        visited = [0] * self.size
        first = 1
        depth = 0
        while first is not None:
            stack = [(first, depth, 0)]
            while len(stack) > 0:
                i, depth, j = stack.pop()
                if j == 0:
                    if handler:
                        handler.visit(i, depth)
                    visited[i-1] = 1
                    yield i
                try:
                    j = self._nodes[i].index(1, j+1)
                    stack.append((i, depth, j))
                    if visited[j-1] == 0:
                        stack.append((j, depth+1, 0))
                except ValueError:
                    if handler:
                        handler.leave(i)
            first = find_first()

    def bfs(self, handler=None):
        def find_first():
            try:
                return visited.index(0)
            except ValueError:
                return None

        visited = [0] * self.size
        first = 1
        depth = 0
        while first is not None:
            queue = [(first, depth)]
            while len(queue) > 0:
                (i, depth), *queue = queue
                if visited[i-1] == 0:
                    if handler:
                        handler.visit(i, depth)
                    visited[i-1] = 1
                    yield i
                else:
                    continue
                j = 0
                while j < self.size:
                    try:
                        j = self._nodes[i].index(1, j+1)
                        queue.append((j, depth+1))
                    except ValueError:
                        break
                if handler:
                    handler.leave(i)
            first = find_first()


class EventHandler(abc.ABC):
    @abc.abstractmethod
    def visit(self, i, depth):
        pass

    @abc.abstractmethod
    def leave(self, i):
        pass


class Logger(EventHandler):
    def __init__(self, n):
        self.log = [(0, 0)] * n
        self.step = 0

    def visit(self, i, depth):
        self.step += 1
        self.log[i-1] = (self.step, depth, 0)

    def leave(self, i):
        self.step += 1
        self.log[i-1] = (self.log[i-1][0], self.log[i-1][1], self.step)

    def by_node(self):
        i = 1
        for discover, depth, finish in self.log:
            yield (i, discover, depth, finish)
            i += 1

def run():
    n = int(input())
    g = AdjacentGraph(n)
    log = Logger(n)

    for i in range(n):
        id_, c, *links = [int(x) for x in input().split()]
        for n in links:
            g.set_adj_node(id_, n)

    for i in g.bfs(log):
        pass

    for node in log.by_node():
        id_, find, dep, exit = node
        print("{} {}".format(id_, dep))


if __name__ == '__main__':
    run()

Submission status: Time Limit Exceeded

Solution code:
import abc


class AdjacentGraph:
    """Implementation adjacency-list Graph.
    Beware ids are between 1 and size.
    """
    def __init__(self, size):
        self.size = size
        self._nodes = [[0] * (size+1) for _ in range(size+1)]

    def set_adj_node(self, id_, adj_id):
        self._nodes[id_][adj_id] = 1

    def __iter__(self):
        self._id = 0
        return self

    def __next__(self):
        if self._id < self.size:
            self._id += 1
            return (self._id, self._nodes[self._id][1:])

        raise StopIteration()

    def dfs(self, handler=None):
        def find_first():
            try:
                return visited.index(0) + 1
            except ValueError:
                return None

        visited = [0] * self.size
        first = 1
        while first is not None:
            stack = [(first, 0, 0)]
            while len(stack) > 0:
                i, depth, j = stack.pop()
                if j == 0:
                    if handler:
                        handler.visit(i, depth)
                    visited[i-1] = 1
                    yield i
                try:
                    j = self._nodes[i].index(1, j+1)
                    stack.append((i, depth, j))
                    if visited[j-1] == 0:
                        stack.append((j, depth+1, 0))
                except ValueError:
                    if handler:
                        handler.leave(i)
            first = find_first()

    def bfs(self, handler=None):
        def find_first():
            try:
                return visited.index(0) + 1
            except ValueError:
                return None

        visited = [0] * self.size
        first = 1
        while first is not None:
            queue = [(first, 0)]
            while len(queue) > 0:
                (i, depth), *queue = queue
                if visited[i-1] == 0:
                    if handler:
                        handler.visit(i, depth)
                    visited[i-1] = 1
                    yield i
                try:
                    j = 0
                    while j < self.size:
                        j = self._nodes[i].index(1, j+1)
                        if visited[j-1] == 0:
                            queue.append((j, depth+1))
                except ValueError:
                    if handler:
                        handler.leave(i)
            first = find_first()


class EventHandler(abc.ABC):
    @abc.abstractmethod
    def visit(self, i, depth):
        pass

    @abc.abstractmethod
    def leave(self, i):
        pass


class Logger(EventHandler):
    def __init__(self, n):
        self.log = [(0, 0)] * n
        self.step = 0

    def visit(self, i, depth):
        self.step += 1
        self.log[i-1] = (self.step, depth, 0)

    def leave(self, i):
        self.step += 1
        self.log[i-1] = (self.log[i-1][0], self.log[i-1][1], self.step)

    def by_node(self):
        i = 1
        for discover, depth, finish in self.log:
            yield (i, discover, depth, finish)
            i += 1

def run():
    n = int(input())
    g = AdjacentGraph(n)
    log = Logger(n)

    for i in range(n):
        id_, c, *links = [int(x) for x in input().split()]
        for n in links:
            g.set_adj_node(id_, n)

    for i in g.bfs(log):
        pass

    reachable = None
    for node in log.by_node():
        id_, find, dep, exit = node
        if id_ > 1 and dep == 0:
            reachable = find - 1

        if reachable is not None and find > reachable:
            dep = -1

        print("{} {}".format(id_, dep))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
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()
    #print(*adj[u-1])

stack = [0]

while stack:
    #print(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()

    #print('current = {}, t = {}'.format(current, t))
    #print('stack', *stack)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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()

Submission status: Accepted

Solution code:
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)]

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#coding: utf-8
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)

Submission status: Accepted

Solution code:
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]}")

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())

adj = [0]*n # adjacent list
d = [-1]*n # distance from the source vertex
c = ['w']*n # the 'color' of each vertex

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

# set the source vertex
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]}')

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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()
    # print('visited:', u)
    for v in range(n):
        # print(u, v)
        if A[u][v] == 1 and d[v] == -1:
            q.put(v)
            d[v] = d[u] + 1

# print('-========')
for i in range(n):
    print(i+1, d[i])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C
# Breadth First Search
# Result:
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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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)  # Dequeue
        distance = distances[node_id]
        for index, candidate in enumerate(matrix[node_id]):
            if candidate == 1 and distances[index] == -1:
                # ???????????¢????¨?????????????????????? node
                queue.append(index)
                distances[index] = distance + 1

    return distances

if __name__ == "__main__":
    # ??????????????????
    # lines = [
    #     "4",
    #     "1 2 2 4",
    #     "2 1 4",
    #     "3 0",
    #     "4 1 3",
    # ]
    lines = sys.stdin.readlines()
    dimension = int(lines[0])
    matrix = [[0 for _ in range(dimension)] for _ in range(dimension)]

    # Set edge info
    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))

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

Solution code:
#!/usr/bin/python3

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())
# [isFind, d, f]
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])

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#!/usr/bin/env 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()

Submission status: Accepted

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