output_description: Print the information of each node in the following format ordered by IDs:
  
  node _id_ : parent = _p_ , depth = _d_ , _type_ , [_c_ 1..._c k_]
  
  _p_ is ID of its parent. If the node does not have a parent, print -1.
  
  _d_ is depth of the node.
  
  _type_ is a type of nodes represented by a string (root, internal node or
  leaf). If the root can be considered as a leaf or an internal node, print
  root.
  
  _c_ 1..._c k_ is the list of children as a ordered tree.
  
  Please follow the format presented in a sample output below.
input_description: The first line of the input includes an integer _n_ , the number of nodes of
  the tree.
  
  In the next _n_ lines, the information of each node _u_ is given in the
  following format:
  
  _id_ _k_ _c_ 1 _c_ 2 ... _c k_
  
  where _id_ is the node ID of _u_ , _k_ is the degree of _u_ , _c_ 1 ... _c k_
  are node IDs of 1st, ... _k_ th child of _u_. If the node does not have a
  child, the _k_ is 0.
attempt: import queue
  from collections import namedtuple
  
  U = namedtuple("U", "id parent depth type children")
  n = int(input())
  
  dic, link = [dict() for _ in range(2)]
  se = set([int(x) for x in range(n)])
  
  for i in range(n):
      tmp = list(map(int, input().split()))
      tmp.reverse()
  
      a, k = [tmp.pop() for _ in range(2)]
      link[a] = []
      for j in range(k):
          b = tmp.pop()
          link[a].append(b)
  
          se.remove(b)
  
  
  def bfs(s):
      q = queue.Queue()
      q.put(U(s, -1, 0, "root", link[s]))
  
      while q.qsize() != 0:
          u0 = q.get()
          dic[u0.id] = u0
  
          for u1 in u0.children:
              children = link[u1]
              node_type = "leaf" if children == [] else "internal node"
              q.put(U(u1, u0.id, u0.depth + 1, node_type, children))
  
  
  bfs(se.pop())
  
  for i in range(n):
      print("node", dic[i].id, end="")
      print(": parent =", dic[i].parent, end="")
      print(", depth =", dic[i].depth, end="")
      print(",", dic[i].type, end="")
      print(",", dic[i].children)
  
problem_description: Rooted Trees
  
  A graph _G_ = (_V_ , _E_) is a data structure where _V_ is a finite set of
  vertices and _E_ is a binary relation on _V_ represented by a set of edges.
  Fig. 1 illustrates an example of a graph (or graphs).
  
  ![](https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ALDS1_7_A_1)  
  **Fig. 1**
  
  A free tree is a connnected, acyclic, undirected graph. A rooted tree is a
  free tree in which one of the vertices is distinguished from the others. A
  vertex of a rooted tree is called "node."
  
  Your task is to write a program which reports the following information for
  each node _u_ of a given rooted tree _T_ :
  
    * node ID of _u_
    * parent of _u_
    * depth of _u_
    * node type (root, internal node or leaf)
    * a list of chidlren of _u_
  
  If the last edge on the path from the root _r_ of a tree _T_ to a node _x_ is
  (_p_ , _x_), then _p_ is the **parent** of _x_ , and _x_ is a **child** of
  _p_. The root is the only node in _T_ with no parent.
  
  A node with no children is an **external node** or **leaf**. A nonleaf node is
  an **internal node**
  
  The number of children of a node _x_ in a rooted tree _T_ is called the
  **degree** of _x_.
  
  The length of the path from the root _r_ to a node _x_ is the **depth** of _x_
  in _T_.
  
  Here, the given tree consists of _n_ nodes and evey node has a unique ID from
  0 to _n_ -1.
  
  Fig. 2 shows an example of rooted trees where ID of each node is indicated by
  a number in a circle (node). The example corresponds to the first sample
  input.
  
  ![](https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ALDS1_7_A_2)  
  **Fig. 2**
samples: [{"input": "13\n    0 3 1 4 10\n    1 2 2 3\n    2 0\n    3 0\n    4 3 5 6 7\n    5 0\n    6 0\n    7 2 8 9\n    8 0\n    9 0\n    10 2 11 12\n    11 0\n    12 0", "output": "node 0: parent = -1, depth = 0, root, [1, 4, 10]\n    node 1: parent = 0, depth = 1, internal node, [2, 3]\n    node 2: parent = 1, depth = 2, leaf, []\n    node 3: parent = 1, depth = 2, leaf, []\n    node 4: parent = 0, depth = 1, internal node, [5, 6, 7]\n    node 5: parent = 4, depth = 2, leaf, []\n    node 6: parent = 4, depth = 2, leaf, []\n    node 7: parent = 4, depth = 2, internal node, [8, 9]\n    node 8: parent = 7, depth = 3, leaf, []\n    node 9: parent = 7, depth = 3, leaf, []\n    node 10: parent = 0, depth = 1, internal node, [11, 12]\n    node 11: parent = 10, depth = 2, leaf, []\n    node 12: parent = 10, depth = 2, leaf, []"}, {"input": "4\n    1 3 3 2 0\n    0 0\n    3 0\n    2 0", "output": "node 0: parent = 1, depth = 1, leaf, []\n    node 1: parent = -1, depth = 0, root, [3, 2, 0]\n    node 2: parent = 1, depth = 1, leaf, []\n    node 3: parent = 1, depth = 1, leaf, []"}]