Problem:
Rooted Trees A graph G = ( V , E ) is a data structure where V is a finite set of vertices and E is a binary relation on V represented by a set of edges. Fig. 1 illustrates an example of a graph (or graphs).   Fig. 1  A free tree is a connnected, acyclic, undirected graph. A rooted tree is a free tree in which one of the vertices is distinguished from the others. A vertex of a rooted tree is called "node." Your task is to write a program which reports the following information for each node u of a given rooted tree T :  node ID of u  parent of u  depth of u  node type (root, internal node or leaf)  a list of chidlren of u  If the last edge on the path from the root r of a tree T to a node x is ( p , x ), then p is the parent of x , and x is a child of p . The root is the only node in T with no parent. A node with no children is an external node or leaf . A nonleaf node is an internal node  The number of children of a node x in a rooted tree T is called the degree of x . The length of the path from the root r to a node x is the depth of x in T . Here, the given tree consists of n nodes and evey node has a unique ID from 0 to n -1. Fig. 2 shows an example of rooted trees where ID of each node is indicated by a number in a circle (node). The example corresponds to the first sample input.   Fig. 2  Input 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 u is given in the following format:  id  k  c 1  c 2 ... c k  where id is the node ID of u , k is the degree of u , c 1 ... c k are node IDs of 1st, ... k th child of u . If the node does not have a child, the k is 0. Output Print the information of each node in the following format ordered by IDs:  node  id : parent = p , depth = d , type , [ c 1 ... c k ]   p is ID of its parent. If the node does not have a parent, print -1 .  d is depth of the node.  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 .  c 1 ... c k is the list of children as a ordered tree. Please follow the format presented in a sample output below. Constraints  1 ≤ n ≤ 100000  Sample Input 1 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 Sample Output 1 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, [] Sample Input 2 4
1 3 3 2 0
0 0
3 0
2 0 Sample Output 2 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, [] Note You can use a left-child, right-sibling representation to implement a tree which has the following data:  the parent of u  the leftmost child of u  the immediate right sibling of u  Reference Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

Solution (Python):
n=int(input())
nodes=[]
for i in range(n):
    nodes.append(input().split())

nodes.sort(key=lambda x:int(x[0]))
ans={}

for i in range(n):
    if int(nodes[i][1]) >=1:
        for j in nodes[i][2:]:
            ans[j]=[nodes[i][0]]

for i in range(n):
    if str(i) not in ans:
        ans[str(i)]=[str(-1)]
        

for key,value in ans.items():
    depth=0
    x=value[0]
    while int(x) != -1:
        x=ans[x][0]
        depth+=1
    ans[key].append(str(depth))



for key in ans.keys():
    ans[key].append(nodes[int(key)][2:])
    if ans[key][0] == '-1':ans[key].append('root')
    elif ans[key][2] == []:ans[key].append('leaf')
    else:ans[key].append('internal node')


for i in range(n):
    I=str(i)
    print('node '+I+': parent = '+ans[I][0]+', depth = '+str(ans[I][1])+', '+ans[I][3]+', ['+', '.join(ans[I][2])+']')

Solution (Python):
class Node:
    def __init__(self, parent, left, right):
        self.parent = parent
        self.left = left
        self.right = right


n = int(input())

node = {k: Node(-1, -1, -1) for k in range(n)}

for u in range(n):
    tmp = list(map(int, input().split()))
    if tmp[1] == 0:
        continue
    node[tmp[0]].left = tmp[2]
    node[tmp[2]].parent = tmp[0]
    prev_sibling = tmp[2] 
    for sib in tmp[3:]:
        node[prev_sibling].right = sib
        node[sib].parent = tmp[0]
        prev_sibling = sib

def get_depth(node, u):
    d = 0
    while node[u].parent is not -1:
        u = node[u].parent
        d += 1
    return d


def list_children(node, u):
    chilren = []
    c = node[u].left
    while c is not -1:
        chilren.append(c)
        c = node[c].right
    return chilren


for i in range(n):
    node_id = i
    node_parent = node[i].parent
    node_depth = get_depth(node, i)
    node_children = list_children(node, i)
 
    if node_parent == -1:
        node_type = "root"
    elif len(node_children) > 0 :
        node_type = "internal node"
    else:
        node_type = "leaf"

    print("node {}: parent = {}, depth = {}, {}, {}".format(node_id, node_parent, node_depth, node_type, node_children))

Solution (Python):
n=int(input())
c_list=[[]]*n
p_list=[-1]*n
for _ in range(n):
    id,k,*c=map(int,input().split())
    c_list[id]=c
    for i in c:
        p_list[i]=id
root=p_list.index(-1)
depth=[0]*n
next=c_list[root].copy()
while next:
    now=next.pop()
    depth[now]=depth[p_list[now]]+1
    next+=c_list[now]
for i in range(n):
    if i==root:
        type="root"
    elif c_list[i]==[]:
        type="leaf"
    else:
        type="internal node"
    print("node {}: parent = {}, depth = {}, {}, {}".format(i,p_list[i],depth[i],type,c_list[i]))

Solution (Python):
n = int(input())
lst = [list(map(int,input().split())) for i in range(n)]
B = [lst[i][0] for i in range(n)]
node = [[] for i in range(n)]

def Insertion_Sort(lst,B,n):
    for i in range(1,n):
        v = B[i]
        w = lst[i]
        j = i-1
        while j>=0 and B[j]>v:
            B[j+1]=B[j]
            lst[j+1]=lst[j]
            j-=1
        B[j+1]=v
        lst[j+1]=w
        
def find_root():
    A = []
    for i in range(n):
        A.extend(lst[i][2:])
    for i in range(n):
        if not i in A:
            return i

def make_node(arg_parent,arg_num, arg_depth):
    if arg_num == root:
        type = "root"
    elif lst[arg_num][1] == 0:
        type = "leaf"
    else:
        type = "internal node"
    children_lst = lst[arg_num][2:]
    node[arg_num] = [arg_parent, arg_depth, type, children_lst]
    for i in children_lst:
        make_node(arg_num, i, arg_depth+1)

Insertion_Sort(lst, B, n)
root = find_root()
make_node(-1, root, 0)

for i in range(n):
    parent, depth, type, children_lst = node[i]
    print(f"node {i}: parent = {parent}, depth = {depth}, {type}, {children_lst}")

Solution (Python):
class node:
    def __init__(self, parent, left, right, depth):
        self.p = parent
        self.l = left
        self.r = right
        self.d = depth

def getDepth(u):
    depth = 0
    c = u
    while T[c].p != -1:
        depth += 1
        c = T[c].p
    T[u].d = depth

def getChildren(u):
    c = T[u].l
    children = []
    while c != -1:
        children.append(c)
        c = T[c].r
    return children

n = int(input())
T = [node(-1, -1, -1, 0) for _ in range(n)]
for i in range(n):
    info = list(map(int, input().split(" ")))
    for j in range(info[1]):
        if j == 0:
            T[info[0]].l = info[2 + j]
        else:
            T[info[2 + j - 1]].r = info[2 + j]
        T[info[2 + j]].p = info[0]

for i in range(n):
    print("node", end = ' ')
    print(i, end = ': ')
    print("parent =", end = ' ')
    print(T[i].p, end = ', ')
    print("depth =", end = ' ')
    getDepth(i)
    print(T[i].d, end = ', ')
    if T[i].p == -1: print("root", end = ', ')
    elif T[i].l == -1: print("leaf", end = ', ')
    else: print("internal node", end = ', ')
    print(getChildren(i))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

tree = []
root_index = []
depths = []


def main():
    n = int(input())

    
    for i in range(n):
        tree.append(Node(i, None, None))
        root_index.append(i)
        depths.append(0)

    for i in range(n):
        node_number, _, *c_list = list(map(int, input().split()))
        tree[node_number].child = c_list

        for c in c_list:
            tree[c].parent = tree[node_number]
            root_index.remove(c)

    root = tree[root_index[0]]
    root.parent = Node(-1, None, None)

    setDepth(root, 0)
    showTree(root)


def setDepth(node, d):
    depths[node.number] = d
    for c in node.child:
        setDepth(tree[c], d + 1)


def getDepth(node_number):
    return depths[node_number]


def showTree(root):
    for node in tree:
        type = ""
        if node.parent.number == -1:
            type = "root"
        elif len(node.child) == 0:
            type = "leaf"
        else:
            type = "internal node"

        print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(str(node.number), str(node.parent.number), str(depths[node.number]), type, node.child))


class Node():
    def __init__(self, number, parent, child):
        self.number = number
        self.parent = parent
        self.child = child


if __name__ == '__main__':
    main()

Solution (Python):





import sys
sys.setrecursionlimit(2**20)  


class Node:
    def __init__(self,
                 parent,
                 left,
                 right):
        self.parent = parent
        self.left = left  
        self.right = right


def get_depth(T: dict, u: int):
    '''
    Tは木の構造と見立てたdict
    uはTのノード
    '''
    d = 0
    while T[u].parent is not None:
        u = T[u].parent
        d += 1  


D = {}  


def get_all_depth(T: dict, u: int, p: int):
    '''
    一度にすべてのノードの深さを取得する関数(再帰的に処理を行う)。
    一気に全体の深さを求めるならばこちらの方がオーダーが小さい。
    pは現在扱う深さ
    '''
    D[u] = p
    
    if T[u].right is not None:
        
        get_all_depth(T, T[u].right, p)
    if T[u].left is not None:
        
        get_all_depth(T, T[u].left, p+1)


def ret_children(T, u):
    chilren = []
    c = T[u].left
    while c is not None:
        chilren.append(c)
        c = T[c].right
    return chilren




def print_for_a_node(T: dict, node: int, D: dict):
    node_type = 'internal node' if T[node].left is not None else 'leaf'
    if T[node].parent is None:
        parent = -1
        node_type = 'root'
    else:
        parent = T[node].parent
    children = ret_children(T, node)

    print(
        f'node {node}: parent = {parent}, depth = {D[node]}, {node_type}, {children}')



n = int(input())

T = {k: Node(None, None, None) for k in range(n)}  
for _ in range(n):
    tmp = list(map(int, input().split()))
    if tmp[1] == 0:  
        continue
    T[tmp[0]].left = tmp[2]  
    T[tmp[2]].parent = tmp[0]  
    prev_sibling = tmp[2]  
    for sib in tmp[3:]:
        T[prev_sibling].right = sib
        T[sib].parent = tmp[0]  
        prev_sibling = sib

for node in range(n):
    if T[node].parent is None:
        get_all_depth(T, node, 0)  
        
        break





for node in range(n):
    print_for_a_node(T, node, D)

Solution (Python):
"""
根付き木の表現

 [INPUT]
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

[OUTPUT]
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, []
"""

class Node():
    def __init__(self, id, children):
        self.id = id
        self.children = children
        self.parent = -1
        self.type = "internal node"
        self.right_sibling = None
        self.depth = None
        

    def set_parent(self):
        if len(self.children) != 0:
            for child_id in self.children:
                node_list[child_id].parent = self.id
        else:
            self.type = "leaf"
        
    def set_depth(self):
        depth = 0
        node = self
        while node.parent != -1:
            node = node_list[node.parent]
            depth += 1

        if depth == 0:
            self.type = "root"
        self.depth = depth

    
    
    
    
    




if __name__=="__main__":
    N = int(input())
    node_list = [None] * N
    for i in range(N):
        input_list = list(map(int, input().split()))
        id = input_list[0]
        children_num = input_list[1]
        children = input_list[2:] if children_num != 0 else []
        node_list[id] = Node(id, children)

    for n in node_list:
        n.set_parent()

    for n in node_list:
        n.set_depth()

    
    
    

    for n in node_list:
        print("node {}: parent = {}, depth = {}, {}, {}".format(n.id, n.parent, n.depth, n.type, n.children))

Solution (Python):
class Node:
	def __init__(self):
		self.parent = -1
		self.depth = 0
		self.child = []
		self.type = "internal node"

global nodes

def setDepth(id, depth):
	nodes[id].depth = depth
	for child_id in nodes[id].child:
		setDepth(child_id, depth + 1)

if __name__ == "__main__":
	n = int(input())
	nodes = []
	for _ in range(n):
		nodes.append(Node())
	for _ in range(n):
		table = list(map(int, input().split()))
		id = table[0]
		child_num = table[1]
		for k in range(child_num):
			child_id = table[k + 2]
			nodes[id].child.append(child_id)
			nodes[child_id].parent = id
	for i in range(n):
		if nodes[i].parent == -1:
			nodes[i].type = "root"
			rootid = i
		elif nodes[i].child == []:
			nodes[i].type = "leaf"
	setDepth(rootid, 0)

	for i in range(n):
		print(f"node {i}: parent = {nodes[i].parent}, depth = {nodes[i].depth}, {nodes[i].type}, {nodes[i].child}")

Solution (Python):
class node():
    def __init__(self, id, parent, child, depth, type_t):
        self.id = id
        self.parent = parent
        self.child = child
        self.depth = depth
        self.type_t = type_t


def add(t, d, i, parent, depth):
    type_t = 'internal node'
    if d[i][1] == 0:
        type_t = 'leaf'
    if depth == 0:
        type_t = 'root'

    child = []
    if not d[i][1] == 0:
        child = d[i][2:]
    new_node = node(i, parent, d[i][2:], depth, type_t)
    t.append(new_node)
    for c in child:
        add(t, d, c, i, depth + 1)


N = int(input())
tree = []
data = [[] for i in range(N)]
for i in range(N):
    data[i] = [int(i) for i in input().split()]

data.sort(key=lambda x: x[0])

root = [True for i in range(N)]
for d in data:
    for c in d[2:]:
        root[c] = False

for i in range(N):
    if root[i]:
        add(tree, data, i, -1, 0)

tree.sort(key=lambda x: x.id)

for t in tree:
    print(f'node {t.id}: parent = {t.parent}, depth = {t.depth}, {t.type_t}, {t.child}')

Solution (Python):
from collections import deque
from sys import stdin
input = stdin.readline

class Element:
    def __init__(self, node):
        self.node = node
        self.parent = -1
        self.depth = 0
        self.status = "internal node"
        self.children = None
    
    def display(self):
        print("node %d: parent = %d, depth = %d, %s, %s"
        %(self.node, self.parent, self.depth, self.status, str(self.children)))
        
N = int(input())

NODE_DICT = {}
ROOT_SEARCH = [True]*N

for loop in range(N):
    DATA = list(map(int, input().split()))
    node = DATA[0]    
    tmp = Element(node)
    tmp.children = DATA[2:]
    NODE_DICT[node] = tmp
    for i in tmp.children:
        ROOT_SEARCH[i] = False
    





for key in range(len(ROOT_SEARCH)):
    if ROOT_SEARCH[key]:
        root = key

def Process(parent):
    for child in parent.children:
        NODE_DICT[child].parent = parent.node
        NODE_DICT[child].depth = parent.depth + 1
    if parent.children == []:
        parent.status = "leaf"
    else:
        for child in parent.children:
            Process(NODE_DICT[child])
    

Process(NODE_DICT[root])
NODE_DICT[root].status = "root"

for i in range(N):
    NODE_DICT[i].display()

Solution (Python):
class Node:
    def __init__(self):
        self.parent_id = -1
        self.depth = 0
        self.children = []

def calc_depth(node_id, arg_depth):
    nodes[node_id].depth = arg_depth
    for child in nodes[node_id].children:
        calc_depth(child, arg_depth+1)

V = int(input())
global nodes
nodes = []

for loop in range(V):
    node = Node()
    nodes.append(node)


for loop in range(V):
    table = list(map(int,input().split()))
    node_id = table[0]
    num = table[1]
    for i in range(num):
        child_id = table[2+i]
        nodes[node_id].children.append(child_id)
        nodes[child_id].parent_id = node_id


for i in range(V):
    if nodes[i].parent_id == -1:
        calc_depth(i,0)
        break

for i in range(V):
    print("node %d: parent = %d, depth = %d, "%(i, nodes[i].parent_id, nodes[i].depth),end="")

    if nodes[i].parent_id == -1:
        print("root,",end = "")
    else:
        if len(nodes[i].children) == 0:
            print("leaf,",end="")
        else:
            print("internal node,",end="")

    print(" [",end="")
    print(', '.join(map(str,nodes[i].children)),end="")
    print("]")

Solution (Python):
n = int(input())

T = []
for _ in range(n):
    t = list(map(int, input().split()))
    T.append(t)

class Tree:
    def __init__(self, n):
        
        self.nodes = {node: {'parent': None, 'children': [], 'depth': None} for node in range(n)}
        
    def add_node_with_child(self, node, childlen):
        for c in childlen:
            self.nodes[node]['children'].append(c)
            self.nodes[c]['parent'] = node
    
    def get_parent(self, node):
        return self.nodes[node]['parent']
    
    def get_children(self, node):
        return self.nodes[node]['children']
        
    def get_depth(self, node):
        if self.nodes[node]['depth'] != None:
            return self.nodes[node]['depth']
        elif self.nodes[node]['parent'] == None:
            self.nodes[node]['depth'] = 0
            return 0
        else:
            depth = self.get_depth(self.nodes[node]['parent']) + 1
            self.nodes[node]['depth'] = depth
            return depth

            
RootedTree = Tree(n)
for t in T:
    if t[1] == 0:
        continue
        
    node = t[0]
    childlen = t[2:]
    RootedTree.add_node_with_child(node, childlen)
    


for node in range(n):
    parent = RootedTree.get_parent(node)
    if parent == None:
        parent = -1
    depth = RootedTree.get_depth(node)
    childlen = RootedTree.get_children(node)
    childlen = ', '.join(list(map(str, childlen)))
    
    if parent == -1:
        node_type = 'root'
    elif childlen == '':
        node_type = 'leaf'
    else:
        node_type = 'internal node'
    
    print('node {}: parent = {}, depth = {}, {}, [{}]'.format(node, parent, depth, node_type, childlen))

Solution (Python):

import sys


class Node:
    def __init__(self):
        self.child = []
        self.parent = -1
        self.type = 'root'


def calc_depth(node):
    global depth_num
    if node.parent != -1:
        depth_num += 1
        calc_depth(tree[node.parent])
    return depth_num


n = int(input())
tree = []
for i in range(n):
    node = Node()
    tree.append(node)

for i in range(n):
    A = list(map(int, sys.stdin.readline().strip().split()))
    if A[2:]:
        tree[A[0]].child = A[2:]
    else:
        tree[A[0]].type = 'leaf'

    for j in A[2:]:
        tree[j].parent = A[0]
        if tree[j].type != 'leaf':
            tree[j].type = 'internal node'

for i in range(n):
    depth_num = 0
    depth = calc_depth(tree[i])
    if n == 1:
        type = 'root'
    else:
        type = tree[i].type
    print('node {}: parent = {}, depth = {}, {}, {}'.format(i, tree[i].parent, depth, type, tree[i].child))

Solution (Python):
import sys
sys.setrecursionlimit(10000)


class Node:

    def __init__(self, _id):
        self.id = _id
        self.children = []
        self.parent = None
        self.__depth = 0
    
    def add(self, node):
        node.parent = self
        self.children.append(node)

    def parent_id(self):
        if self.parent is None:
            return -1
        else:
            return self.parent.id

    def node_type(self):
        if self.parent is None:
            return 'root'
        elif len(self.children) == 0:
            return 'leaf'
        else:
            return 'internal node'

    def children_ids(self):
        return list(map(lambda n: n.id, self.children))

    def depth(self):
        if self.parent is None:
            return 0
        else:
            return self.parent.depth() + 1

    def __repr__(self):
        return 'node {}: parent = {}, depth = {}, {}, {}'.format(
            self.id, self.parent_id(), self.depth(), self.node_type(), self.children_ids())


def main():
    n = int(input())
    nodes = [Node(i) for i in range(n)]
    for _ in range(n):
        ID, _, *c_s = map(int, input().split(' '))
        for c in c_s:
            nodes[ID].add(nodes[c])
    for n in nodes:
        print(n)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
from enum import Enum
import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

class Node:
    def __init__(self):
        self.parent_id = -1
        self.depth = 0
        self.children = []

global nodes

def calc_depth(node_id,arg_depth):

    nodes[node_id].depth = arg_depth
    for child in nodes[node_id].children:
        calc_depth(child, arg_depth+1)


V = int(input())

nodes = []

for loop in range(V):
    node = Node()
    nodes.append(node)


for loop in range(V):

    table = list(map(int,input().split()))
    node_id = table[0]
    num = table[1]

    for i in range(num):
        child_id = table[2+i]
        nodes[node_id].children.append(child_id)
        nodes[child_id].parent_id = node_id



for i in range(V):
    if nodes[i].parent_id == -1:
        calc_depth(i,0)
        break


for i in range(V):

    print("node %d: parent = %d, depth = %d, "%(i,nodes[i].parent_id,nodes[i].depth),end = "")

    if nodes[i].parent_id == -1:
        print("root,",end = "")
    else:
        if len(nodes[i].children) == 0: 
            print("leaf,",end = "")
        else: 
            print("internal node,",end = "")

    print(" [",end = "")
    print(', '.join(map(str,nodes[i].children)),end = "")
    print("]")

Solution (Python):
import sys
input = sys.stdin.readline

class Node:
    def __init__(self):
        self.parent = -1
        self.typ = "leaf"

def dfs(G, v, d=0):
    G[v].depth = d
    for child in G[v].childlen:
        dfs(G, child, d+1)

def main():
    N = int(input())
    G = [Node() for _ in range(N)]
    for _ in range(N):
        idx, k, *childlen = map(int, input().split())
        G[idx].childlen = childlen
        if k:
            G[idx].typ = "internal node"
        for child in childlen:
            G[child].parent = idx
    root = [i for i, x in enumerate(G) if x.parent == -1][0]
    G[root].typ = 'root'
    dfs(G, root)
    for i, x in enumerate(G):
        print('node {}: parent = {}, depth = {}, {}, [{}]'.format(i, x.parent, x.depth, x.typ, ', '.join(list(map(str, x.childlen)))))

if __name__ == '__main__': main()

Solution (Python):
class treeNode:
    def __init__(self, x):
        self.val = x
        self.children = []
    
n = int(input())
rootL = list(range(n))
hashMap = {}
index = 0
while index < n:
    listI = list(map(int, input().split()))
    if listI[0] in hashMap:
        node = hashMap[listI[0]]
        childrenL = []
        if listI[1] == 0:
            pass
        else:
            for child in listI[2:]:
                rootL.remove(child)
                if child in hashMap:
                    childN = hashMap[child]
                else:
                    childN = treeNode(child)
                childrenL.append(childN)
                hashMap[child] = childN
        node.children = childrenL
    else:
        hashMap[listI[0]] = treeNode(listI[0])
        childrenL = []
        for child in listI[2:]:
            rootL.remove(child)
            if child in hashMap:
                childN = hashMap[child]
            else:
                childN = treeNode(child)
            childrenL.append(childN)
            hashMap[child] = childN
        hashMap[listI[0]].children = childrenL
    index+=1

root = hashMap[rootL[0]]
answerL = ['']*n

def lookNode(node, parentV, depth):
    answer = ''
    answer+='node '+str(node.val)+': '
    answer+='parent = '+str(parentV)+', '
    answer+='depth = '+str(depth)+', '
    if depth == 0:
        answer+='root,'
    elif node.children == []:
        answer+='leaf,'
    else:
        answer+='internal node,'
    childrenL = []
    for child in node.children:
        childrenL.append(child.val)
    answerL[node.val] = [answer, childrenL]
    for child in node.children:
        lookNode(child, node.val, depth+1)
lookNode(root, -1, 0)
for ans in answerL:
    print(ans[0], ans[1])

Solution (Python):
import sys

class Node():

	def __init__(self,id,k,children):
		
		self.id = id
		self.k = k
		self.children = children
		self.parent = -1
		self.depth = 0

def find_root(Nodes,node):

	if node.parent == -1:
		return node.id

	return find_root(Nodes,Nodes[node.parent])

def define_depth(Nodes,node):

	if node.k == 0: 
		return True

	for child in node.children: 
		Nodes[child].depth = node.depth + 1
		define_depth(Nodes,Nodes[child])

def sort(Nodes):

	for i in range(len(Nodes)-1):
		for j in range(i+1,len(Nodes)):

			if Nodes[i].id > Nodes[j].id:

				Nodes[i],Nodes[j] = Nodes[j],Nodes[i]

def test():

	n = int(sys.stdin.readline())
	child = []
	Nodes = [Node(0,0,child)] * n
	root = 0

	
	for i in range(n):

		inputs = list(map(int,sys.stdin.readline().split()))
		id = inputs[0]
		k = inputs[1]
		child = []
		for j in range(k):
			child.append(inputs[2+j])

		tmp_node = Node(id,k,child)
		Nodes[id] = tmp_node

	

	
	for node in Nodes:

		for i in range(node.k):
			
			Nodes[node.children[i]].parent = node.id
	
	
	root = find_root(Nodes,Nodes[0])

	

	
	define_depth(Nodes,Nodes[root])

	for i in range(n):

		print(f"node {Nodes[i].id}: parent = {Nodes[i].parent}, depth = {Nodes[i].depth}, ",end='')

		if Nodes[i].parent == -1:
			print(f"root, [",end='')
		elif Nodes[i].k == 0:
			print(f"leaf, [",end='')
		else:
			print(f"internal node, [",end='')

		for j in range(Nodes[i].k - 1):
			print(f"{Nodes[i].children[j]}, ",end='')
		if Nodes[i].k != 0:
			print(f"{Nodes[i].children[Nodes[i].k-1]}]")
		else:
			print("]")


if __name__ == "__main__":
	test()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
P = [-1]*n
C = [[] for i in range(n)]
D = [[] for i in range(n)]
T = [[] for i in range(n)]

for i in range(n):
  s = [int(i) for i in input().split()]
  id = s[0]
  k = s[1]
  if k >= 1:
    c = s[2:]
    C[id] = c
    for j in range(k):
      P[c[j]] = id
  else:
    T[id] = "leaf"

for i in range(n):
  if P[i] == -1:
    root = i
    T[i] = "root"
  elif T[i] == []:
    T[i] = "internal node"

H = deque()
H.append(root)
D[root] = 0

while H:
  x = H.popleft()
  for nx in C[x]:
    H.append(nx)
    D[nx] = D[x] + 1

for i in range(n):
  print("node {}: parent = {}, depth = {}, {}, {}".format(i,P[i],D[i],T[i],C[i]))

Solution (Python):
import sys

n = int(input())

"""子情報を入れる'c'、親情報を入れる'p'、深さを記録する'd'の、3つの辞書を作る"""
c, p, d = {}, {}, {}

"""根のid, depthを引数とすることで、全てのnodeの深さを'd'に記録する関数"""
def checkdepth(id, depth):
    d[id] = depth
    for child in c[id]:
        checkdepth(child, depth+1)

for i in sys.stdin:
    i = i.split()
    """i[0]=id, i[1]=k, i[2:]=children"""
    c[i[0]] = i[2:]
    for j in i[2:]:
        p[j] = i[0]

"""親の集合から子の集合を差し引いて残ったものは根（root）になる"""
root = (set(c) - set(p)).pop()
p[root] = '-1'
checkdepth(root, 0)

for i in range(n):
    i = str(i)
    if p[i] == '-1':
        nodetype = 'root'
    else:
        if c[i]:
            nodetype = 'internal node'
        else:
            nodetype = 'leaf'
    children = ', '.join(c[i])
    print('node {}: parent = {}, depth = {}, {}, [{}]'.format(i, p[i], d[i], nodetype, children))

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
n=int(input())
inp=[list(map(int,input().split())) for i in range(n)]
inp.sort(key=lambda tup:tup[0])
data=[[-1]*3 for i in range(n)]
D=[-1]*n

for e in inp:
    for i in range(2,len(e)):
        data[e[i]][0]=e[0]
        if i==2:
            data[e[0]][1]=e[i]
        else:
            data[l][2]=e[i]
        l=e[i]

for i in range(n):
    if data[i][0]==-1:
        r=i

def defth(node,p):
    D[node]=p
    if data[node][1]!=-1:
        defth(data[node][1],p+1)
    if data[node][2]!=-1:
        defth(data[node][2],p)

defth(r,0)

for i in range(n):
    if i==r:sta='root'
    elif len(inp[i])==2:sta='leaf'
    else: sta='internal node'
    print(f'node {i}: parent = {data[i][0]}, depth = {D[i]}, {sta}, {inp[i][2:]}')