陈远龙精品编程（信奥赛） 助力信奥赛学子取得优秀的成绩

题目描述

给定一棵有根树的信息，请你编写个程序输出这棵树的各个节点的信息：

• 当前节点的编号
• 当前节点的种类（root, internal node，leaf，分别代表：根、内部节点、叶子节点）
• 当前节点的父节点编号
• 当前节点的子节点列表
• 当前节点的深度（根节点的深度为0）

根节点（root）是没有父节点的那个节点，只有1个根节点

叶子节点（leaf）是没有子节点的那些节点

内部节点（internal node）是除了根节点和叶子节点外的其他节点

这里，给定的树由 n 个节点组成，每个节点都有一个从 0 到 n-1 的唯一ID编号（或者是值域）。

下图 显示了一个有根树的示例，其中每个节点的 ID 由圆圈中的数字（节点）表示。该示例对应于第一个样例输入。

输入格式

输入的第一行包含一个整数 n，表示树的节点数。

接下来的 n 行中，每行提供一个节点 u 的信息，格式如下：

id k c1 c2 ... ck

其中 id 是节点 u 的 ID，k 是 u 的度，c1 ... ck 是 u 的第 1 到第 k 个子节点的 ID。如果节点没有子节点，则 k 为 0。

输出格式

按 ID 顺序（从小到大的顺序）以下面的格式打印每个节点的信息：

node id: parent = p, depth = d, type, [c1...ck]

p 是其父节点的 ID。如果节点没有父节点，打印 -1。

d 是节点的深度，根节点的深度为0

type 是表示节点类型的字符串（根节点 root、内部节点 internal node或叶节点 leaf）。如果只有1个节点，则视为根节点，打印 root。

c1...ck 是按顺序排列的子节点列表。

请遵循下面的示例输出格式。

输入输出样例

输入样例	输出样例
13 0 3 1 4 10 1 2 2 3 2 0 3 0 4 3 5 6 7 5 0 6 0 7 2 8 9 8 0 9 0 10 2 11 12 11 0 12 0	node 0: parent = -1, depth = 0, root, [1, 4, 10] node 1: parent = 0, depth = 1, internal node, [2, 3] node 2: parent = 1, depth = 2, leaf, [] node 3: parent = 1, depth = 2, leaf, [] node 4: parent = 0, depth = 1, internal node, [5, 6, 7] node 5: parent = 4, depth = 2, leaf, [] node 6: parent = 4, depth = 2, leaf, [] node 7: parent = 4, depth = 2, internal node, [8, 9] node 8: parent = 7, depth = 3, leaf, [] node 9: parent = 7, depth = 3, leaf, [] node 10: parent = 0, depth = 1, internal node, [11, 12] node 11: parent = 10, depth = 2, leaf, [] node 12: parent = 10, depth = 2, leaf, []
4 1 3 3 2 0 0 0 3 0 2 0	node 0: parent = 1, depth = 1, leaf, [] node 1: parent = -1, depth = 0, root, [3, 2, 0] node 2: parent = 1, depth = 1, leaf, [] node 3: parent = 1, depth = 1, leaf, []

数据范围与提示

100%的数据：$1 \le n \le 100000$

测试点数目

共10个测试点，每个测试点10分

时间与内存限制

每个测试点时间：1000ms（1.0s），内存：256MiB

输入输出模式

本OJ支持两种输入输出模式