//二分木
//参考：https://onlinejudge.u-aizu.ac.jp/solutions/problem/ALDS1_7_A/review/1911082/emine/C%23
//参考：https://onlinejudge.u-aizu.ac.jp/solutions/problem/ALDS1_7_B/review/1911248/emine/C%23
//片方の枝が-1の時むり

using System;
using System.Text;
using System.Collections.Generic;
namespace tst
{
    class Program
    {
        class Node
        {
            internal int parent;
            internal int[] child=new int[2] {-1,-1 };
            internal int sibling;//きょうだいのindex
            internal int degree;//子供の数
            internal int depth;
            internal int height;
            internal string type;
            public Node()
            {
                parent = -1;
                sibling = -1;
                degree = 2;
                depth = 0;
                height = -1;
                type = "";
            }

        }
        public static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            Node[] nodes = new Node[n];
            for (int i = 0; i < n; i++)
            {
                nodes[i] = new Node();
            }
            //depthやheigthを決めるスタック
            Stack<Node> stk1 = new Stack<Node>();
            Stack<Node> stk2 = new Stack<Node>();
            //入力
            for (int i=0; i<n; i++)
            {
                string[] S_In = Console.ReadLine().Split(' ');
                int[] In = new int[] {int.Parse(S_In[0]), int.Parse(S_In[1]), int.Parse(S_In[2])};
                if(In[1]==-1 && In[2] == -1)
                {
                    nodes[In[0]].height = 0;
                    nodes[In[0]].degree = 0;
                    nodes[In[0]].type = "leaf";
                    stk2.Push(nodes[In[0]]);
                }
                else
                {
                    for (int j = 1; j <= 2; j++)
                    {
                        if (In[j] != -1)
                        {
                            nodes[In[j]].parent = In[0];
                            nodes[In[0]].child[j - 1] = In[j];
                            if (j == 1) nodes[In[1]].sibling = In[2];
                            if (j == 2) nodes[In[2]].sibling = In[1];
                        }
                        else
                        {
                            nodes[In[0]].degree = 1;
                        }
                    }
                }
            }
            //type入れる
            for (int i = 0; i < n; i++)
            {
                if (nodes[i].parent == -1)
                {
                    nodes[i].type = "root";
                    if (n != 1)
                    {
                        stk1.Push(nodes[i]);//rootのindexをスタックの先頭へ
                    }
                    //Console.WriteLine("いれました"+nodes[i]);

                }
                else if (nodes[i].type == "")
                {
                    nodes[i].type = "internal node";
                }
            }
            //depthに関するスタックループ
            while (stk1.Count > 0)
            {
                Node temp = stk1.Pop();
                //Console.WriteLine("だしました" + temp.type);
                for (int i=0; i<=1; i++)
                {
                    if (temp.child[i] != -1)
                    {
                        //Console.WriteLine(temp.child[i - 1]);
                        nodes[temp.child[i]].depth = temp.depth + 1;
                        if (nodes[temp.child[i]].type == "internal node")
                        {
                            stk1.Push(nodes[temp.child[i]]);
                            //Console.WriteLine("いれました" + nodes[i].type);
                        }
                    }
                }
            }
            //heightに関するスタックループ
            while (stk2.Count > 0)
            {
                Node temp = stk2.Pop();
                if (temp.parent != -1)//root以外なら
                {
                    nodes[temp.parent].height = Math.Max(nodes[temp.parent].height, temp.height + 1);
                    stk2.Push(nodes[temp.parent]);
                }
            }


            for (int i = 0; i < n; i++)
            {
                Console.WriteLine("node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}", i, nodes[i].parent, nodes[i].sibling, nodes[i].degree, nodes[i].depth, nodes[i].height, nodes[i].type);
            }

        }

    }
}


Measured memory_bytes: 18472