using System;
using System.Collections.Generic;
using System.Linq;
// Q024 二分木の表現 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_B&lang=jp
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("9");
WillReturn.Add("0 1 4");
WillReturn.Add("1 2 3");
WillReturn.Add("2 -1 -1");
WillReturn.Add("3 -1 -1");
WillReturn.Add("4 5 8");
WillReturn.Add("5 6 7");
WillReturn.Add("6 -1 -1");
WillReturn.Add("7 -1 -1");
WillReturn.Add("8 -1 -1");
//node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root
//node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node
//node 2: parent = 1, sibling = 3, degree = 0, depth = 2, height = 0, leaf
//node 3: parent = 1, sibling = 2, degree = 0, depth = 2, height = 0, leaf
//node 4: parent = 0, sibling = 1, degree = 2, depth = 1, height = 2, internal node
//node 5: parent = 4, sibling = 8, degree = 2, depth = 2, height = 1, internal node
//node 6: parent = 5, sibling = 7, degree = 0, depth = 3, height = 0, leaf
//node 7: parent = 5, sibling = 6, degree = 0, depth = 3, height = 0, leaf
//node 8: parent = 4, sibling = 5, degree = 0, depth = 2, height = 0, leaf
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
struct NodeInfoDef
{
internal int LeftNodeID;
internal int RightNodeID;
}
static Dictionary<int, NodeInfoDef> mNodeInfoDict = new Dictionary<int, NodeInfoDef>();
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();
// 処理01 入力をDictに保存
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
NodeInfoDef WillAdd;
WillAdd.LeftNodeID = wkArr[1];
WillAdd.RightNodeID = wkArr[2];
mNodeInfoDict.Add(wkArr[0], WillAdd);
}
// 処理02 木の根をO(n)で求める
var ChildNodeSet = new HashSet<int>();
foreach (var EachPair in mNodeInfoDict) {
ChildNodeSet.Add(EachPair.Value.LeftNodeID);
ChildNodeSet.Add(EachPair.Value.RightNodeID);
}
int RootNode = -1;
foreach (int EachKey in mNodeInfoDict.Keys) {
if (ChildNodeSet.Contains(EachKey) == false) {
RootNode = EachKey;
}
}
// 処理03 根からDFSで各ノードの情報を求める
List<JyoutaiDef> JyoutaiList = ExecDFS(RootNode);
JyoutaiList.Sort((A, B) => A.NodeID.CompareTo(B.NodeID));
// 処理04 各ノードの情報を出力する
foreach (JyoutaiDef EachJyoutai in JyoutaiList) {
string NodeInfo = "";
int NodeID = EachJyoutai.NodeID;
if (NodeID == RootNode) {
NodeInfo = "root";
}
else if (mNodeInfoDict[NodeID].LeftNodeID == -1
&& mNodeInfoDict[NodeID].RightNodeID == -1) {
NodeInfo = "leaf";
}
else {
NodeInfo = "internal node";
}
int Sibling = DeriveSibling(NodeID, EachJyoutai.ParentNode);
int Degree = DeriveDegree(NodeID);
int Height = DeriveHeight(NodeID);
string FormatStr = "node {0}: parent = {1}, sibling = {2}, ";
FormatStr += "degree = {3}, depth = {4}, height = {5}, {6}";
Console.WriteLine(FormatStr, EachJyoutai.NodeID, EachJyoutai.ParentNode,
Sibling, Degree, EachJyoutai.Depth, Height, NodeInfo);
}
}
struct JyoutaiDef
{
internal int NodeID;
internal int ParentNode;
internal int Depth;
}
// 処理03 根からDFSで各ノードの情報を求める
static List<JyoutaiDef> ExecDFS(int pRootNode)
{
var WillReturn = new List<JyoutaiDef>();
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.NodeID = pRootNode;
WillPush.ParentNode = -1;
WillPush.Depth = 0;
Stk.Push(WillPush);
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
WillReturn.Add(Popped);
Action<int> PushAct = pChildNode =>
{
if (pChildNode == -1) return;
WillPush.NodeID = pChildNode;
WillPush.ParentNode = Popped.NodeID;
WillPush.Depth = Popped.Depth + 1;
Stk.Push(WillPush);
};
PushAct(mNodeInfoDict[Popped.NodeID].LeftNodeID);
PushAct(mNodeInfoDict[Popped.NodeID].RightNodeID);
}
return WillReturn;
}
// 兄弟ノードを返す
static int DeriveSibling(int pCurrNode, int pParentNode)
{
if (pParentNode == -1) return -1;
int LeftNodeID = mNodeInfoDict[pParentNode].LeftNodeID;
int RightNodeID = mNodeInfoDict[pParentNode].RightNodeID;
if (LeftNodeID != -1 && LeftNodeID != pCurrNode) return LeftNodeID;
if (RightNodeID != -1 && RightNodeID != pCurrNode) return RightNodeID;
return -1;
}
// 度数を求める
static int DeriveDegree(int pCurrNode)
{
int WillReturn = 0;
if (mNodeInfoDict[pCurrNode].LeftNodeID != -1) WillReturn++;
if (mNodeInfoDict[pCurrNode].RightNodeID != -1) WillReturn++;
return WillReturn;
}
struct DeriveHeightJyoutaiDef
{
internal int NodeID;
internal int Level;
}
// ノードからDFSで高さを求める
static int DeriveHeight(int pCurrNode)
{
int WillReturn = 0;
var Stk = new Stack<DeriveHeightJyoutaiDef>();
DeriveHeightJyoutaiDef WillPush;
WillPush.NodeID = pCurrNode;
WillPush.Level = 0;
Stk.Push(WillPush);
while (Stk.Count > 0) {
DeriveHeightJyoutaiDef Popped = Stk.Pop();
WillReturn = Math.Max(WillReturn, Popped.Level);
Action<int> PushAct = pChildNode =>
{
if (pChildNode == -1) return;
WillPush.NodeID = pChildNode;
WillPush.Level = Popped.Level + 1;
Stk.Push(WillPush);
};
PushAct(mNodeInfoDict[Popped.NodeID].LeftNodeID);
PushAct(mNodeInfoDict[Popped.NodeID].RightNodeID);
}
return WillReturn;
}
}