output_description: 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.
input_description: 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$.
attempt: import collections
  
  
  def breadth_first_search(g, check, length):
      q = collections.deque()
      q.append(1)
      check[1] = 1
      length[1] = 0
      while len(q) != 0:
          v = q.popleft()
          for u in g[v]:
              if check[u] == 0:
                  check[u] = 1
                  length[u] = length[v] + 1
                  q.append(u)
  
      return length
  
  
  def main():
      N = int(input())
      g = []
      g.append([])
      for i in range(N):
          tmp = input().split()
          tmp_ls = []
          for i in range(int(tmp[1])):
              tmp_ls.append(int(tmp[i + 2]))
          g.append(tmp_ls)
  
      check = [0] * (N + 1)
      length = [0] * (N + 1)
      ans = breadth_first_search(g, check, length)
      for i in range(N):
          node_num = i + 1
          if ans[node_num] == 0 and i != 0:
              ans[node_num] = -1
          print(node_num, ans[node_num])
  
  
  main()
  
problem_description: 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$.
samples: [{"input": "4\n    1 2 2 4\n    2 1 4\n    3 0\n    4 1 3", "output": "1 0\n    2 1\n    3 2\n    4 1"}]