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: # Tree - Rooted Trees
  class Node:
      def is_leaf(self):
          return self.depth > 0 and len(self.degree) == 0
  
      def __init__(self, id):
          self.id = id
          self.parent = None
          self.sibling = None
          self.degree = []
          self.depth = 0
          self.height = 0
  
      def __str__(self):
          p = self.parent.id if self.parent else -1
          s = self.sibling.id if self.sibling else -1
          d = len(self.degree)
          typ = "root"
          if self.depth > 0:
              typ = "internal node"
          if d == 0 and self.depth > 0:
              typ = "leaf"
          h = self.height
          return "node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}".format(
              self.id, p, s, d, self.depth, h, typ
          )
  
  
  def calc_cld_depth(nd):
      cs = nd.degree
      for c in cs:
          c.depth = nd.depth + 1
          calc_cld_depth(c)
  
  
  n = int(input())
  rbt = [Node(i) for i in range(n)]
  for i in range(n):
      id, left, right = map(int, input().split())
      tgt = rbt[id]
      l, r = None, None
      if not left == -1:
          l = rbt[left]
          l.depth += tgt.depth + 1
          l.parent = tgt
          calc_cld_depth(l)
          tgt.degree.append(l)
      if not right == -1:
          r = rbt[right]
          r.depth += tgt.depth + 1
          r.parent = tgt
          calc_cld_depth(r)
          tgt.degree.append(r)
      if (not left == -1) and (not right == -1):
          l.sibling, r.sibling = r, l
      if left == -1 and right == -1:
          if tgt.parent:
              tgt.depth = tgt.parent.depth + 1
  # calc height
  for c in rbt:
      h = 0
      if c.is_leaf():
          c.height = h
          p = c.parent
          while p:
              h += 1
              if p.height < h:
                  p.height = h
              p = p.parent
  for t in rbt:
      print(t)
  
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)"}]