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
  
  
  class Node:
      NIL = -1
  
      def __init__(self, p=NIL, l=NIL, r=NIL, d=-1, h=-1):
          self.p = p
          self.l = l
          self.r = r
          self.d = d
          self.h = h
  
      def __repr__(self):
          return "Node({}, {}, {}, {})".format(self.p, self.l, self.r, self.d)
  
  
  def root_of(T):
      return [u.p for u in T].index(Node.NIL)
  
  
  def sibling_of(T, id):
      p = T[T[id].p]
      return p.r if p.l == id else p.l
  
  
  def degree_of(T, id):
      l = 0 if T[id].l == Node.NIL else 1
      r = 0 if T[id].r == Node.NIL else 1
      return l + r
  
  
  def calc_depth(T):
  
      def rec(id, depth):
          nonlocal T
  
          T[id].d = depth
          if T[id].l != Node.NIL:
              rec(T[id].l, depth + 1)
          if T[id].r != Node.NIL:
              rec(T[id].r, depth + 1)
  
      rec(root_of(T), 0)
  
  
  def calc_height(T):
  
      def rec(id):
          nonlocal T
  
          l = 0 if T[id].l == Node.NIL else rec(T[id].l) + 1
          r = 0 if T[id].r == Node.NIL else rec(T[id].r) + 1
          T[id].h = max(l, r)
          return T[id].h
  
      rec(root_of(T))
  
  
  def type_of(T, id):
      if T[id].p == Node.NIL:
          return "root"
      elif T[id].l == Node.NIL and T[id].r == Node.NIL:
          return "leaf"
      else:
          return "internal node"
  
  
  def read_nodes(T):
      for line in stdin:
          id, l, r = [int(x) for x in line.split()]
          T[id].l = l
          if l != Node.NIL:
              T[l].p = id
          T[id].r = r
          if r != Node.NIL:
              T[r].p = id
  
  
  def print_nodes(T):
      for id in range(len(T)):
          print("node {}: ".format(id), end="")
          print("parent = {}, ".format(T[id].p), end="")
          print("sibling = {}, ".format(sibling_of(T, id)), end="")
          print("degree = {}, ".format(degree_of(T, id)), end="")
          print("depth = {}, ".format(T[id].d), end="")
          print("height = {}, ".format(T[id].h), end="")
          print(type_of(T, id))
  
  
  def main():
      n = int(stdin.readline())
      T = [Node() for _ in range(n)]
  
      read_nodes(T)
      calc_depth(T)
      calc_height(T)
      print_nodes(T)
  
  
  main()
  
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)"}]