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

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)


def solve():

    n = iip(False)

    edge = {}
    for i in range(n):
        d = iip()
        if len(d) == 2:
            continue
        for j in d[2:]:
            edge[(i+1, j)] = True

    #print(edge)

    que = deque([(1, 0)])
    r = [10**12 for i in range(n)]
    while que:
        node = que.popleft()
        dis = min(node[1], r[node[0]-1])
        r[node[0]-1] = dis
        for target in range(n+1):
            if (node[0], target) in edge and r[target-1] == 10**12:
                que.append((target, dis+1))
                #print(target, dis+1)

    #print(r)

    for i, j in enumerate(r, 1):
        if j == 10**12:
            j = -1
        print(i, j)






#####################################################ライブラリ集ここから



def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=False):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    if isinstance(l, list):
        l = l[0] # 間違って要素１個のタプルを渡されても受け取る
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): # 関数を二分探索
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        #print(x)
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            #print(r, l)
            l = x

    #print(l, r)
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import copy
import sys
import fractions
# import numpy as np
# import statistics
import decimal
import heapq
import collections
import itertools
import bisect

# from operator import mul

sys.setrecursionlimit(100001)


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

# ===FUNCTION===

def getInputIntList():
    outputDataList = []
    inputData = input().split()
    outputDataList = [int(n) for n in inputData]

    return outputDataList


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

d = [-1] * n

for a in adj:
    for i in range(len(a)):
        a[i] -= 1

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

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

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
seen = [-1]*(N+1)

todo = deque()


def bfs(v):
    u = v-1
    next_v = graph[u][2:]
    for i in next_v:
        if seen[i] == -1:
            seen[i] = seen[v] + 1
            todo.append(i)


todo.append(1)
seen[1] = 0

while len(todo) > 0:
    bfs(todo.popleft())

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

Submission status: Accepted

Solution code:
#from collections import deque
import sys

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

#def mypopleft(que, index):
#    if len(que) > index:
#        return que.pop(index)
#    else:
#        return []


def main():
    # input
    n = int(input())

    graph = []
    for i in range(n):
        u, k, *tmp = [int(i) for i in readline().split()]
        graph.append(tmp)
    
    #print(graph)
    d = [-1]*n
    #que = deque([1])
    que = [1]
    #count = 0
    d[0] = 0
    check = []

    while True:
        v = que.pop(0)
        #print(v)
        #count += 1
        #print(d)
        for u in graph[v-1]:
            #print(u)
            if d[u-1] == -1:
                d[u-1] = d[v-1] + 1
                que.append(u)
        if len(que) == 0:
            break
    
    for i in range(n):
        print("{} {}".format(i+1, d[i]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
#グラフ入力受取
G = [[] for _ in range(N)]
for _ in range(N):
    a = list(map(int, input().split()))
    for i in a[2:]:
        G[a[0]-1].append(i-1)

#頂点1をスタートとした探索
dist = [-1]*N
que = deque()
dist[0] = 0
que.append(0)
while len(que)!=0:
    v = que.popleft()
    for nv in G[v]:
        if dist[nv] == -1:
            dist[nv] = dist[v]+1
            que.append(nv)
        
for i in range(N):
    print(str(i+1) + ' ' + str(dist[i]))

Submission status: Accepted

Solution code:
from collections import deque

def bfs(adj_mat, d):
    Q = deque()
    N = len(d)
    color = ["W" for n in range(N)]

    Q.append(0)
    d[0] = 0

    while len(Q) != 0:
        u = Q.popleft()

        for i in range(N):
            if adj_mat[u][i] == 1 and color[i] == "W":
                color[i] = "G"
                d[i] = d[u] + 1
                Q.append(i)

        color[u] = "B"

    for i in range(N):
        if color[i] != "B":
            d[i] = -1

def Main():
    N = int(input())

    adj_mat = [[0 for n in range(N)] for n in range(N)]
    d = [0] * N

    for n in range(N):
        u, k , *V = map(int, input().split())

        if k > 0:
            for i in V:
                adj_mat[n][i - 1] = 1

    bfs(adj_mat, d)

    for n in range(N):
        print("{} {}".format(n + 1, d[n]))
Main()

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_11_C

from collections import deque


class Data:
    def __init__(self, index, depth):
        super().__init__()
        self.index = index
        self.depth = depth


if __name__ == "__main__":
    n = int(input())
    d = {}
    for _ in range(n):
        u, k, *li = list(map(int, input().split()))
        d[u] = li

    queue = deque()

    result = {}
    for i in range(n):
        result[i+1] = -1

    depth = 0
    queue = deque()
    queue.appendleft(Data(index=1, depth=0))
    while queue:
        data = queue.pop()
        index = data.index
        depth = data.depth
        if result[index] != -1:
            continue
        result[index] = depth

        for child in d[index]:
            queue.appendleft(Data(index=child, depth=depth+1))

    for k, v in result.items():
        print(k, v)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
M = [[0]*n for _ in range(n)]
d = [-1]*n
st = [0]*n
for _ in range(n):
    i = [int(i) for i in input().split()]
    u = i[0]
    k = i[1]
    V = i[2:]
    for v in V: M[u-1][v-1] = 1

def bfs(s):
    Q = deque()
    Q.append(s)
    st[s] = 1
    d[s] = 0
    while Q:
        u = Q.popleft()
        for v in range(n):
            if M[u][v] and st[v] == 0:
                st[v] = 1
                Q.append(v)
                d[v] = d[u]+1
        st[u] = 2
    return

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

Submission status: Accepted

Solution code:
from collections import deque

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

for i in range(n):
  u,k,*v = map(int, input().split())
  v = [w-1 for w in v]
  adj[u-1].extend(v)

queue = deque([0])
ans = [-1] * n
ans[0] = 0

while queue:
  now = queue.popleft()
  
  for u in adj[now]:
    if ans[u] < 0:# 未訪問
      ans[u] = ans[now] + 1
      queue.append(u)

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

Submission status: Accepted

Solution code:
# Breadth First Search
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
E = (tuple(map(int, input().split())) for _ in range(n))
E = [[v-1 for v in V] for i, k, *V in E]

q = deque()
visited = [False]*n
D = [-1]*n

# 初期条件
s = 0
q.append(s)
visited[s] = True
D[s] = 0

# BFS
while q:
    v = q.popleft()
    for u in E[v]:
        if not visited[u]:
            q.append(u)
            visited[u] = True
            D[u] = D[v]+1


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

Submission status: Accepted

Solution code:
from collections import deque

def main():

    inf = 1000000007
    n = int(input())
    e = [[] for _ in range(n)]
    d = [inf]*n

    for i in range(n):
        m = list(map(int,input().split()))
        for j in range(2,len(m)):
            e[m[0]-1].append(m[j]-1)

    d[0] = 0
    dq = deque([])
    dq.append([0,0])
    while dq:
        c,v = dq.popleft()
        for u in e[v]:
            if d[u]==inf:
                d[u] = c+1
                dq.append([c+1,u])

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
INF = 1145141919810364364334
s = [None]
r = [None]

n = int(input())
for _ in range(n):
    temp = list(map(int,input().split()))
    s.append(temp[2:])
    
d = [INF] * (n+1)

d[1] = 0
q = deque()
q.append(1)

while q:
    x = q.popleft()
    for i in s[x]:
        if d[i] == INF:
            q.append(i)
            
        d[i] = min(d[x] + 1 , d[i])
        
for i in range(1,n+1):
    if d[i] == INF:
        d[i] = -1
    print(i,d[i])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
g = []
for i in range(n):
    t = na()
    u = t[0] - 1
    k = t[1]
    v = [x-1 for x in t[2:]]
    g.append(v)
dist = [-1] * n
que = deque()
dist[0] = 0
que.append(0)
while que:
    #print(que)
    v = que.popleft()
    for nv in g[v]:
        if dist[nv] != -1: continue
        dist[nv] = dist[v] + 1
        que.append(nv)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


N = int(input())

edge = {}
for _ in range(N):
    tmp = inpl()
    u, k = tmp[:2]
    edge[u] = tmp[2:]

d = {i: -1 for i in range(1, N + 1)}
d[1] = 0
Q = deque()
Q.append(1)
while Q:
    v = Q.popleft()
    for nv in edge[v]:
        if d[nv] != -1:
            continue
        d[nv] = d[v] + 1
        Q.append(nv)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(15000)
n = int(sys.stdin.readline())

ret = []
inp = sys.stdin.readlines()
G = [None]*(n+1)
depths = [-1]*(n+1)

for i in range(1,n+1):
  v = list(map(int,inp[i-1].split()))
  G[v[0]] = list(map(int,v[2:]))
#print(G)

nodes = [1]
depth = 0
while nodes:
  new = []
  for i in nodes:
    if depths[i] == -1:
      depths[i] = depth
      new += G[i]
    #print(i,nodes,depth,depths)
  depth += 1
  nodes = new

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

Submission status: Accepted

Solution code:
import queue


def bfs(g, s=1):
    global q

    dist = [-1] * len(g)
    dist[1] = 0
    q = queue.Queue()
    q.put(s)

    while not q.empty():
        v = q.get()
        if not G[v][1]:
            continue
        for vi in G[v][2:]:
            if dist[vi] >= 0:
                continue
            q.put(vi)
            dist[vi] = dist[v] + 1

    return dist


n = int(input())
G = [None]
for i in range(n):
    G.append(list(map(int, input().split())))

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import deque

n = int(input())

edges = [[] for _ in range(n)]
for _ in range(n):
    line = list(map(int, input().split()))
    u = line[0] - 1
    if len(line) != 2:
        v_list = line[1:]
        for v in v_list:
            edges[u].append(v - 1)
# print(n, edges)

dist = [-1 for _ in range(n)]
que = deque()


def dfs(que, dist):
    while len(que) > 0:
        v = que.popleft()

        for v_adj in edges[v]:
            if dist[v_adj] == -1:
                dist[v_adj] = dist[v] + 1
                que.append(v_adj)


dist[0] = 0
que.appendleft(0)
dfs(que, dist)

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

Submission status: Accepted

Solution code:
n=int(input())
G=[]
for i in range(n):
    u,k,*l=map(int,input().split())
    G.append(l)
#print(G)

#BFS
from collections import deque
def bfs(G,v,p):
    que=deque()
    que.append((v,p))
    log=[-1]*n
    log[0]=0
    while que:
        #queの先頭を取り出す
        V,P=que.popleft()
        for next_v in G[V-1]:
            if log[next_v-1]!=-1:continue
            log[next_v-1]=log[V-1]+1
            que.append((next_v,V))
    return log

log=bfs(G,1,-1)
for i in enumerate(log,1):
    print(*i)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
g = [list(map(int, input().split()))[2:] for _ in range(n)]
que = deque([0])
dist = [-1] * n
dist[0] = 0  # 初期条件
while que:  # queが空なるまで
    u = que.popleft()  # queの左から順に取り出す
    for v in g[u]:
        v -= 1  # 0-indexedに変更
        if dist[v] == -1:  # 未探索の時
            dist[v] = dist[u] + 1  # 最短距離を記録
            que.append(v)  # queに追加
for i in range(n):
    print(i + 1, dist[i])

Submission status: Accepted

Solution code:
ii = lambda : int(input())
li = lambda : list(map(int,input().split()))

from collections import deque

class tree:
    def __init__(self,n):
        self.n = n
        self.arr = [[] for i in range(self.n)]
        self.root = [-1]*n

    def add_arr(self, u, v):
        if v[0] != 0:
            self.arr[u-1] = v[1:]

n = ii()
t = tree(n)
for i in range(n):
    uk = li()
    t.add_arr(uk[0],uk[1:])
l = deque()
l.append(0)
t.root[0] = 0
while len(l)>0:
    p = l.popleft()
    for i in t.arr[p]:
        if t.root[i-1] == -1:
            t.root[i-1] = t.root[p]+1
            l.append(i-1)

for k,i in enumerate(t.root):
    print(k+1,i)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
Ps = []
for _ in range(n):
  lis = list(map(int, input().split()))
  if len(lis)>2:
    Ps.append(lis[2:])
  else:
    Ps.append([])
ans = [-1]*n
ans[0] = 0
queue = deque()
checked = deque()
[queue.append([p, 1]) for p in Ps[0]]
checked.append(1)
while queue:
  t, pa = queue.popleft()
  if not t in checked:
    for i in Ps[t-1]:
      queue.append([i, t])
    ans[t-1] = ans[pa-1]+1
    checked.append(t)
for i, a in enumerate(ans):
  print(i+1, a)

Submission status: Accepted

Solution code:
n = int(input())
G = {}
D = [-1] * n
for _ in range(n):
    A = list(map(int, input().split()))
    G[A[0] - 1] = [a - 1 for a in A[2:]]

# print(G)

q = [(0, 0)]
while len(q) > 0:
    v, d = q[0]
    del q[0]
    if D[v] >= 0:
        continue
    D[v] = d

    for nv in G[v]:
        q.append((nv, d+1))

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

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
	que=deque([])
	que.append(0)
	v[0]=0
	
	while que:
		p=que.popleft()
		for l in L[p]:
			if v[l-1]==-1:
				que.append(l-1)
				v[l-1]=v[p]+1
	
n=int(input())
L=[]
for i in range(n):
	A=[]
	A=list(map(int,input().split()))
	L.append(A[2:])
v=[-1]*n
bfs()
for i in range(n):
	print(i+1,v[i])

Submission status: Accepted

Solution code:
n = int(input())

A = [[] for i in range(n)]

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

f_inf = float("inf")
B = [[f_inf for i in range(2)] for j in range(n)]
B[0][1] = 0

for i in range(n):
  B[i][0] = i+1

def dbs(a):
  global order
  l = len(A[a-1])-2
  if l:
    for i in range(l):
      depth = B[a-1][1]+1
      b = A[a-1][i+2]
      if not b in order or depth < B[b-1][1]:
        B[b-1][1] = depth
        order.append(b)
        dbs(b)

order = [1]
dbs(1)

for i in range(n):
  if B[i][1] == f_inf:
    B[i][1] = -1
  print(" ".join(map(str, B[i])))

Submission status: Accepted

Solution code:
n=int(input())
dic=[[] for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a=a[2:]
    dic[i]=list(map(lambda x:x-1,a))

from collections import deque
d=deque()
d.append(0) #始点
completed=[False]*n
distance=[999]*n
distance[0]=0
while d:
    now=d.popleft()
    completed[now]=True
    for x in dic[now]: #次の頂点探し
        if completed[x]==False: #その頂点に進んでもよいか
            distance[x]=min(distance[now]+1,distance[x])  #処理
            d.append(x)
for i in range(n):
    if distance[i]==999:
        distance[i]=-1
    print(i+1,distance[i])

Submission status: Accepted

Solution code:
from collections import deque
def bfs(g,v):
    q=deque([v]) ; vis=[0]*n
    vis[v]=1 ; stg[v]=0
    while q:
        v=q[0]
        for p in g[v]:
            if vis[p]==0: 
                q.append(p)
                vis[p]=1
                stg[p]=stg[v]+1
        q.popleft()
n=int(input())
g=[[] for i in range(n)]
for _ in range(n):
    a=[int(i)-1 for i in input().split()]
    for i in a[2:]: g[a[0]].append(i)
stg=[-1]*n
bfs(g,0)
for i in range(n):
    print(i+1,stg[i])

Submission status: Accepted

Solution code:
n = int(input())

adj_list = [[] for _ in range(n + 1)]

for i in range(n):
    tmp = list(map(int, input().split()))
    u = tmp[0]
    k = tmp[1]
    for v in range(2, 2 + k):
        adj_list[u].append(tmp[v])

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

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

for idx, d in enumerate(d):
    if idx != 0:
        print("%d %d" % (idx, d))

Submission status: Accepted

Solution code:
import queue

n = int(input())
v = [[]]
for _ in range(n):
    edges = sorted([int(x) for x in input().split()][2:])
    v.append(edges)
answers = [[idx, -1] for idx in range(n + 1)]
q = queue.Queue()
q.put(1)

answers[1][1] = 0
while not q.empty():
    node = q.get()
    for next_node in v[node]:
        if answers[next_node][1] != -1:
            continue
        q.put(next_node)
        answers[next_node][1] = answers[node][1] + 1

for idx, time in answers[1:]:
    print(idx, time)

Submission status: Accepted

Solution code:
import queue

N = int(input())
L = [list(map(int,input().split())) for _ in range(N)]
V = [(i+1) for i in range(N)]
E = []
for i in range(N):
    for j in range(len(L[i])-2):
        E.append((i+1,L[i][j+2]))

class Graph:
    def __init__(self,v,e):
        self.v = v
        self.e = e
        self.v_visited = [False for _ in range(N)]
    def visited(self,v):
        self.v_visited[v-1] = True

q = queue.Queue()
g = Graph(V,E)
TS = [-1 for _ in range(N)]

def bfs(u):
    q.put(u)
    g.visited(u)
    TS[u-1] = 0
    while not q.empty():
        u = q.get()
        for v in g.v:
            if (u,v) in g.e and g.v_visited[v-1] == False:
                q.put(v)
                g.visited(v)
                TS[v-1] = TS[u-1]+1
bfs(1)

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

Submission status: Accepted

Solution code:
n = int(input())
E = [[]]*n

for i in range(n):
    inputs = list(map(int, input().split()))
    if inputs[1]>0:
        for e in inputs[2:]:
            E[i] = E[i] + [e-1]

visited = [-1]*n
dist = [-1]*n
dist[0] = 0

from collections import deque

d = deque()
d.append(0)
visited[0] = 1

while len(d):
    nd = d.popleft()
    #print(nd, E[nd])
    for e in E[nd]:
        #print(e)
        if visited[e]<0:
            d.append(e)
            dist[e] = dist[nd] + 1
            visited[e] = 1
    #print(d, visited, dist, len(d))
            

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

Submission status: Accepted

Solution code:
n = int(input())

graphs = []

for _ in range(n):
    graphs.append(list(map(int, input().split()))[2:])


def bfs(graphs, seen_points, score, scores, queue):
    while len(queue) > 0:
        start_point = queue.pop(0)
        if seen_points[start_point - 1] == 2:
            continue
        else:
            next_points = [
                point for point in graphs[start_point - 1] if seen_points[point - 1] == 0]
            if len(next_points) >= 1:
                score += 1
                for point in next_points:
                    queue.append(point)
                    if seen_points[point - 1] == 0:
                        seen_points[point - 1] = 1
                        scores[point - 1] = scores[start_point - 1] + 1
                seen_points[start_point - 1] = 2


seen_points = [0 for _ in range(n)]
scores = [-1 for _ in range(n)]
scores[0] = 0
queue = [1]
bfs(graphs, seen_points, 0, scores, queue)

for index, score in enumerate(scores):
    print(index + 1, score)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

n = int(input())
dis = [-1] * n
info = [list(map(int, input().split())) for _ in range(n)]

stack = [[0, 0]]
ans = 0
while len(stack) > 0:
    num = stack.pop(0)
    if dis[num[0]] == -1:
        dis[num[0]] = num[1]
    for i in info[num[0]][2:]:
        if dis[i-1] == -1:
            stack.append([i - 1, num[1] + 1])
for i in range(n):
    print(str(i+1) + " " + str(dis[i]))

Submission status: Accepted

Solution code:
import sys
# sys.stdin = open('input.txt')
from collections import deque

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

def bfs(s):
    status[s] = VISITING
    distance[s] = 0
    Q.append(s)
    while len(Q) > 0:
        u = Q.popleft()
        for v in range(n):
            if matrix[u][v] and status[v] == NOT_VISITED:
                status[v] = VISITING
                distance[v] = distance[u] + 1
                Q.append(v)
        status[u] = VISITED

n = int(input())
matrix = [[0]*n for i in range(n)]
INFTY = 1 << 21
distance = [INFTY] * n

NOT_VISITED = 0 # WHITE
VISITING = 1 # GRAY
VISITED = 2 # BLACK
status = [NOT_VISITED] * n
Q = deque()

fillMatrix()
bfs(0)

for i in range(n):
    ans = []
    ans.append(i+1)
    if distance[i] == INFTY:
        distance[i] = -1
    ans.append(distance[i])
    ans = map(str, ans)
    print(' '.join(ans))

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(50000)

n = int(input())

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


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


bfs([1])

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

Submission status: Accepted

Solution code:
#=============================================================================
# Breadth First Search
#=============================================================================
import queue

N=int(input())
Graph=[[] for _ in range(N+1)]
dist=[-1 for _ in range(N+1)]
for i in range(1,N+1):
    Graph[i]=list(map(int,input().split()))[2:]


que=queue.Queue()
que.put(1)
dist[1]=0
while not que.empty():
    v=que.get()
    for nv in Graph[v]:
        if dist[nv] != -1:
            continue
        dist[nv]=dist[v]+1
        que.put(nv)
for i in range(1,N+1):
    print(i,dist[i],sep=" ")