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: # coding: utf-8
  import queue
  
  
  class Node:
      def __init__(self, myNum, childNums):
          self.myNum = myNum
          self.parentNum = -1
          self.childNums = childNums
          self.nodeType = ""
          self.depth = -1
  
  
  n = int(input().rstrip())
  nodes = []
  # 入力を使ってクラスに放り込む
  for i in range(n):
      line = [int(i) for i in input().rstrip().split()]
      childNums = [i for i in line[2:]]
      nodes.append(Node(line[0], childNums))
  # nodesを節点順にソートする
  nodes = sorted(nodes, key=lambda x: x.myNum)
  # 親を計算する
  for node in nodes:
      for num in node.childNums:
          nodes[num].parentNum = node.myNum
  
  # type を求める
  for node in nodes:
      if node.parentNum == -1:
          node.nodeType = "root"
          rootNum = node.myNum
      elif not node.childNums:
          node.nodeType = "leaf"
      else:
          node.nodeType = "internal node"
  
  # depth を計算する
  q = queue.Queue()
  q.put(nodes[rootNum])
  nodes[rootNum].depth = 0
  while not q.empty():
      nd = q.get()
      for c in nd.childNums:
          nodes[c].depth = nd.depth + 1
          q.put(nodes[c])
  
  # アウトプット
  for node in nodes:
      print(
          "node {0}: parent = {1}, depth = {2}, {3}, {4}".format(
              node.myNum, node.parentNum, node.depth, node.nodeType, node.childNums
          )
      )
  
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, []"}]