output_description: Print the information of each node in the following format:
  
  node _id_ : parent = _p_ , sibling = _s_ , degree = _deg_ , depth = _dep_ ,
  height = _h_ , _type_  
  
  _p_ is ID of its parent. If the node does not have a parent, print -1.
  
  _s_ is ID of its sibling. If the node does not have a sibling, print -1.
  
  _deg_ , _dep_ and _h_ are the number of children, depth and height of the node
  respectively.
  
  _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.
  
  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 is given in the following
  format:
  
  _id left right_
  
  _id_ is the node ID, _left_ is ID of the left child and _right_ is ID of the
  right child. If the node does not have the left (right) child, the
  _left_(_right_) is indicated by -1.
attempt: if __name__ == "__main__":
      parent, children, depths, sibling, heights = {}, {}, {}, {}, {}
      n = int(input())
      for _ in range(n):
          i, left, right = input().split()
          if left == "-1" and right == "-1":
              children[i] = None
              continue
          if left == "-1" or right == "-1":
              child = left if right == "-1" else right
              children[i] = [child]
          else:
              children[i] = [left, right]
          for child in children[i]:
              parent[child] = i
  
      root = (set(children) - set(parent)).pop()
      parent[root] = "-1"
      sibling[root] = "-1"
  
      def get_degree(i):
          if children[i] is None:
              return 0
          return len(children[i])
  
      def get_type(i):
          if parent[i] == "-1":
              return "root"
          if children[i] is None:
              return "leaf"
          return "internal node"
  
      def set_depth(i, depth):
          depths[i] = depth
          if children[i] is not None:
              for child in children[i]:
                  set_depth(child, depth + 1)
  
      def set_sibling(i, s):
          sibling[i] = s
          childs = children[i]
          if childs is not None:
              if len(childs) == 1:
                  set_sibling(childs[0], "-1")
              else:
                  set_sibling(childs[0], childs[1])
                  set_sibling(childs[1], childs[0])
  
      def set_height(i):
          if children[i] is None:
              heights[i] = 0
              return 0
          childs = children[i]
          if len(childs) == 1:
              heights[i] = set_height(childs[0]) + 1
              return heights[i]
          heights[i] = max(set_height(childs[0]), set_height(childs[1])) + 1
          return heights[i]
  
      set_depth(root, 0)
      set_sibling(root, "-1")
      set_height(root)
      for i in map(str, range(n)):
          print(
              "node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(
                  i,
                  parent[i],
                  sibling[i],
                  get_degree(i),
                  depths[i],
                  heights[i],
                  get_type(i),
              )
          )
  
problem_description: Binary Tree
  
  A rooted binary tree is a tree with a root node in which every node has at
  most two children.
  
  Your task is to write a program which reads a rooted binary tree _T_ and
  prints the following information for each node _u_ of _T_ :
  
    * node ID of _u_
    * parent of _u_
    * sibling of _u_
    * the number of children of _u_
    * depth of _u_
    * height of _u_
    * node type (root, internal node or leaf)
  
  If two nodes have the same parent, they are **siblings**. Here, if _u_ and _v_
  have the same parent, we say _u_ is a sibling of _v_ (vice versa).
  
  The height of a node in a tree is the number of edges on the longest simple
  downward path from the node to a leaf.
  
  Here, the given binary tree consists of _n_ nodes and evey node has a unique
  ID from 0 to _n_ -1.
samples: [{"input": "9\n    0 1 4\n    1 2 3\n    2 -1 -1\n    3 -1 -1\n    4 5 8\n    5 6 7\n    6 -1 -1\n    7 -1 -1\n    8 -1 -1", "output": "node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root\n    node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node\n    node 2: parent = 1, sibling = 3, degree = 0, depth = 2, height = 0, leaf\n    node 3: parent = 1, sibling = 2, degree = 0, depth = 2, height = 0, leaf\n    node 4: parent = 0, sibling = 1, degree = 2, depth = 1, height = 2, internal node\n    node 5: parent = 4, sibling = 8, degree = 2, depth = 2, height = 1, internal node\n    node 6: parent = 5, sibling = 7, degree = 0, depth = 3, height = 0, leaf\n    node 7: parent = 5, sibling = 6, degree = 0, depth = 3, height = 0, leaf\n    node 8: parent = 4, sibling = 5, degree = 0, depth = 2, height = 0, leaf\n    \n\n![](https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ALDS1_7_B_1)"}]