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: from sys import stdin
  
  N = int(input())
  nodes = [None] * N
  sibling = [None] * N
  dep = [0] * N
  parent_list = [None] * N
  degree = [0] * N
  
  
  class node_tree:
      def __init__(self, node):
          self.node = node
          self.left = None
          self.right = None
          self.brother = None
          self.up = None
  
  
  for i in range(N):
      node, left, right = list(map(int, (stdin.readline().strip().split())))
      if nodes[node] is not None:
          parent = nodes[node]
      else:
          parent = node_tree(node)
      if left != -1:
          if nodes[left] is not None:
              left_node = nodes[left]
          else:
              left_node = node_tree(left)
          parent.left = left_node
          left_node.up = parent
  
      if right != -1:
          if nodes[right] is not None:
              right_node = nodes[right]
          else:
              right_node = node_tree(right)
          parent.right = right_node
          right_node.up = parent
      if left != -1 and right != -1:
          left_node.brother = right_node
          right_node.brother = left_node
      if left != -1:
          nodes[left] = left_node
      if right != -1:
          nodes[right] = right_node
      nodes[node] = parent
  
  
  def search_root(u):
      if u.up != None:
          return search_root(u.up)
      else:
          return u.node
  
  
  oya = search_root(nodes[0])
  
  
  def search_depth(u, p):
      dep[u.node] = p
      if u.right is not None and u.left is not None:
          degree[u.node] = 2
      elif u.left is not None:
          degree[u.node] = 1
      elif u.right is not None:
          degree[u.node] = 1
      else:
          degree[u.node] = 0
  
      if u.right is not None:
          parent_list[u.right.node] = u.node
          search_depth(u.right, p + 1)
      if u.left is not None:
          parent_list[u.left.node] = u.node
          search_depth(u.left, p + 1)
  
  
  def search_height(u):
      h1, h2 = 0, 0
      if u.right is not None:
          h1 = search_height(u.right) + 1
      if u.left is not None:
          h2 = search_height(u.left) + 1
      return max(h1, h2)
  
  
  def search_sib(u):
      if u.brother is not None:
          sibling[u.node] = u.brother.node
          sibling[u.brother.node] = u.node
      if u.left is not None:
          search_sib(u.left)
      if u.right is not None:
          search_sib(u.right)
  
  
  search_sib(nodes[oya])
  search_depth(nodes[oya], 0)
  word_list = ["internal node", "leaf"]
  for i in range(N):
      height = search_height(nodes[i])
      if height >= 1:
          word = word_list[0]
      else:
          word = word_list[1]
      if i == oya:
          parent_list[oya] = -1
          sibling[oya] = -1
          word = "root"
      if sibling[i] is None:
          sibling[i] = -1
      print(
          (
              "node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s"
              % (
                  nodes[i].node,
                  parent_list[i],
                  sibling[i],
                  degree[i],
                  dep[i],
                  height,
                  word,
              )
          )
      )
  
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)"}]