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):
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'depth', 'type', 'c']
    def __init__(self, id):
        self.id = id
        self.p = -1
        self.depth = -1
        self.type = "leaf"
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, depth = {self.depth}, {self.type}, {self.c}"
n = int(input())
li = tuple(Tree(i) for i in range(n))
for _ in range(n):
    id, k, *c = map(int, readline().split())
    if k != 0:
        li[id].type = "internal node"
        li[id].c = c
        for j in c:
            li[j].p = id
root = 0
while li[root].p != -1:
    root = li[root].p
li[root].type = "root"
li[root].depth = 0
def depth_check(id, d):
    d += 1
    for i in li[id].c:
        li[i].depth = d
        if li[i].type != "leaf":
            depth_check(i, d)
depth_check(root, 0)
print("\n".join(map(str, li)))

Solution (Python):
class tree:
    def __init__(self,name,parent):
        self.name = name
        self.parent = parent
        
        
n = int(input())
trees = {str(i):tree(str(i),'-1') for i in range(n)}
child = {}

for i in range(n):
    s = [i for i in input().split()]
    p = s[0]
    child[p] = s[2:]
    s_t = s[2:]
    for j in range(len(s_t)):
        trees[s_t[j]] = tree(s_t[j],p)

def getDepth(u):
    d = 0
    while trees[u].parent != '-1':
        u = trees[u].parent
        d += 1
    return d

def getChildren(u):
    c = []
    for i in trees.values():
        if i.parent == u:
            c.append(i.name)
    return c

for i in range(n):
    
    par = trees[str(i)].parent
    dep = getDepth(str(i))
    ch = [int(i) for i in child[str(i)]]
    
    if par == '-1':sit = 'root'
    elif len(ch) != 0:sit = 'internal node'
    else:sit = 'leaf'
    
    print('node {}: parent = {}, depth = {}, {}, {}'.format(i,par,dep,sit,ch))

Solution (Python):
import collections

def search(node, elems, tree, depth):
    elems[node].append(depth)
    if elems[node][0] == -1:
        state = 'root'
    elif not tree[node]:
        state = 'leaf'
    else:
        state = 'internal node'
    elems[node].append(state)
    elems[node].append(tree[node])
    depth += 1
    for c in tree[node]:
        search(c, elems, tree, depth)
    
if __name__ == '__main__':
    n = int(input())
    tree = collections.defaultdict(list)
    elems = collections.defaultdict(list)
    
    parents = list()
    node_list = list()
    for _ in range(n):
        hoge = [int(x) for x in input().split()]
        node_list.append(hoge[0])
        tree[hoge[0]]
        for childs in range(hoge[1]):
            tree[hoge[0]].append(hoge[childs+2])
    
    for key, value in tree.items():
        for v in value:
            elems[v].append(key)
    for node in node_list:
        if not elems[node]:
            parents.append(node)
            elems[node].append(-1)
    
    for p in parents:
        search(p, elems, tree, 0)
        
    for key, value in sorted(elems.items()):
        print('node {0}: parent = {1[0]}, depth = {1[1]}, {1[2]}, '.format(key, value), end='')
        print (value[-1])

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t={}
p={}
d={}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):i=str(i);print('node',i+':','parent =',p[i]+',','depth =',d[i]+',','root,'if'-1'==p[i]else'internal node,'if t[i]else'leaf,',list(map(int,t[i])))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):i=str(i);print('node',i+':','parent =',p[i]+',','depth =',d[i]+',','root,'if'-1'==p[i]else'internal node,'if t[i]else'leaf,',list(map(int,t[i])))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):i=str(i);print('node',i+':','parent =',p[i]+',','depth =',d[i]+',','root,'if'-1'==p[i]else'internal node,'if t[i]else'leaf,',list(map(int,t[i])))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):i=str(i);print('node',i+':','parent =',p[i]+',','depth =',d[i]+',','root,'if'-1'==p[i]else'internal node,'if t[i]else'leaf,',list(map(int,t[i])))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):i=str(i);print('node',i+':','parent =',p[i]+',','depth =',d[i]+',','root,'if'-1'==p[i]else'internal node,'if t[i]else'leaf,',list(map(int,t[i])))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):i=str(i);print('node',i+':','parent =',p[i]+',','depth =',d[i]+',','root,'if'-1'==p[i]else'internal node,'if t[i]else'leaf,',list(map(int,t[i])))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):i=str(i);print('node',i+':','parent =',p[i]+',','depth =',d[i]+',','root,'if'-1'==p[i]else'internal node,'if t[i]else'leaf,',list(map(int,t[i])))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):
 i=str(i)
 f='root'if'-1'==p[i]else'internal node'if t[i]else'leaf'
 print(f'node {i}: parent = {p[i]}, depth = {d[i]}, {f}, {list(map(int,t[i]))}')

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):
 i=str(i)
 f='root'if'-1'==p[i]else'internal node'if t[i]else'leaf'
 print(f'node {i}: parent = {p[i]}, depth = {d[i]}, {f}, {list(map(int,t[i]))}')

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):
 i=str(i)
 f='root'if'-1'==p[i]else'internal node'if t[i]else'leaf'
 print(f'node {i}: parent = {p[i]}, depth = {d[i]}, {f}, {list(map(int,t[i]))}')

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):
 i=str(i)
 f='root'if'-1'==p[i]else'internal node'if t[i]else'leaf'
 print(f'node {i}: parent = {p[i]}, depth = {d[i]}, {f}, {list(map(int,t[i]))}')

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):
 i=str(i)
 f='root'if'-1'==p[i]else'internal node'if t[i]else'leaf'
 print(f'node {i}: parent = {p[i]}, depth = {d[i]}, {f}, {list(map(int,t[i]))}')

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):i=str(i);print(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]")

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):i=str(i);print(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]")

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):i=str(i);print(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]")

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):i=str(i);print(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]")

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
import sys
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
input()
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
import sys
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
input()
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
import sys
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
input()
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
import sys
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
input()
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
import sys
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
input()
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
import sys
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
input()
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
input()
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
input()
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
input()
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
input()
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
input()
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Solution (Python):
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
n=int(input())
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,range(n))))

Solution (Python):
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
n=int(input())
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,range(n))))

Solution (Python):
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
n=int(input())
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,range(n))))

Solution (Python):
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
n=int(input())
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,range(n))))

Solution (Python):
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
n=int(input())
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,range(n))))

Solution (Python):
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
n=int(input())
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,range(n))))

Solution (Python):
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
n=int(input())
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,range(n))))

Solution (Python):
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
n=int(input())
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,range(n))))

Solution (Python):
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
n=int(input())
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,range(n))))

Solution (Python):
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
n=int(input())
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,range(n))))

Solution (Python):
class Vertex:
    _id = -1
    _children = []
    _parent = -1
    _depth = 0
    _type = "root"

    def __init__(self, i, c):
        self._id = i
        self._children = c

    def getId(self):
        return self._id

    def getChildren(self):
        return self._children

    def getParent(self):
        return self._parent

    def getDepth(self):
        return self._depth

    def getType(self):
        return self._type

    def setParent(self, p):
        self._parent = p

    def setDepth(self, d):
        self._depth = d

    def setType(self, t):
        self._type = t

    def print(self):
        print("node {}: parent = {}, depth = {}, {}, {}".format(self._id, self._parent, self._depth, self._type, self._children))


n = int(input())
tree = [0 for i in range(n)]


for i in range(n):
    u = list(map(int, input().split(' ')))
    tree[u[0]] = Vertex(u[0], u[2:u[1]+2])


for w in tree:
    for c in w.getChildren():
        tree[c].setParent(w.getId())
        tree[c].setType("internal node")


for w in tree:
    if w.getChildren() == []:
        w.setType("leaf")
    if w.getParent() == -1:
        w.setType("root")


def dfs(v, depth):
    v.setDepth(depth)
    for child in v.getChildren():
        dfs(tree[child], depth+1)


root = tree[0]
for w in tree:
    if w.getType() == "root":
        root = w

dfs(root, 0)


for w in tree:
    w.print()

Solution (Python):
class Tree:
    nodes = []
    def __init__(self, root = None):
        None
    def insert(self, label, children = []):
        if children != []:
            for i in children:
                self.nodes[label].children.append(self.nodes[i])
                self.nodes[i].parent = self.nodes[label]
                self.nodes[i].type_ = "internal node"
    def depth(self, node):
        if node.children == []:
            node.type_ = "leaf"
        else:
            for i in node.children:
                i.depth = node.depth + 1
                self.depth(i)

class Node:
    def __init__(self, label, children = []):
        self.label = label
        self.type_ = "root"
        self.depth = 0
        self.parent = -1
        self.children = [] 

tree = Tree()
n = int(input())
for i in range(n):
    tree.nodes.append(Node(i))
for i in range(n):
    children = []
    label, num, *children = map(int, input().split())
    tree.insert(label, children)
for i in tree.nodes:
    if i.parent == -1:
        tree.depth(i)
        None
if n == 1:
    tree.nodes[0].type_ = "root"
for i in tree.nodes:
    print("node {0:}: parent = {1:}, depth = {2:}, {3:}, ".\
            format(i.label, i.parent if i.parent == -1 else i.parent.label,\
            i.depth, i.type_), end = "")
    print([i.label for i in i.children])

Solution (Python):
NIL = -1

class Node:
    parent = NIL
    left = NIL
    right = NIL

n = int(input())
t = [Node() for i in range(n)]

for i in range(n):
    tmp = list(map(int, input().split()))
    id = tmp.pop(0)
    k = tmp.pop(0)
    c = tmp
    if k != 0:
        for j in c:
            t[j].parent = id
        t[id].left = c[0]
        for j in range(len(c)-1):
            t[c[j]].right = c[j+1]

def getdepth(u):
    d = 0
    while t[u].parent != NIL:
        u = t[u].parent
        d += 1
    return d

def getchildren(u):
    c = t[u].left
    result = []
    while c != NIL:
        result.append(c)
        c = t[c].right
    return result

for i in range(n):
    d = getdepth(i)
    c = getchildren(i)
    if d == 0:
        v = "root"
    elif c == []:
        v = "leaf"
    else:
        v = "internal node"
    print('node {}: parent = {}, depth = {}, {}, [{}]'.format(i, t[i].parent, d, v, ', '.join(map(str, c))))

Solution (Python):

class TreeNode:
    def __init__(self, nodeid):
        self.nodeid = nodeid
        self.parent = None
        self.sibling = None
        self.child = None
        self.depth = 0

    def node_type(self):
        if self.parent is None:
            return 'root'
        elif self.child is None:
            return 'leaf'
        else:
            return 'internal node'

    def parent_nodeid(self):
        if self.parent is None:
            return -1
        else:
            return self.parent.nodeid

    def child_nodeids(self):
        if self.child is not None:
            yield self.child.nodeid
            yield from self.child.sibling_nodeids()

    def sibling_nodeids(self):
        s = self.sibling
        stack = []
        while s is not None:
            stack.append(s.nodeid)
            s = s.sibling
        while len(stack) > 0:
            yield stack.pop()

    def get_depth(self):
        if self.node_type() != 'root' and self.depth == 0:
            self.depth = self.parent.get_depth() + 1

        return self.depth

    def add_child(self, node):
        if self.child is None:
            self.child = node
            self.child.parent = self
        else:
            self.child.add_sibling(node)

    def add_sibling(self, node):
        node.parent = self.parent
        node.sibling = self.sibling
        self.sibling = node

    def __str__(self):
        return ('node {}: parent = {}, depth = {}, {}, [{}]'.format(
                self.nodeid, self.parent_nodeid(), self.get_depth(),
                self.node_type(),
                ", ".join([str(i) for i in self.child_nodeids()])))


class Tree:
    def __init__(self):
        self.nodes = {}

    def node(self, nodeid):
        if nodeid not in self.nodes:
            self.nodes[nodeid] = TreeNode(nodeid)

        return self.nodes[nodeid]

    def sorted_nodes(self):
        for nodeid in sorted(self.nodes.keys()):
            yield self.nodes[nodeid]


def run():
    c = int(input())
    tree = Tree()

    for _ in range(c):
        nodeid, deg, *cs = [int(i) for i in input().split()]
        node = tree.node(nodeid)
        for c in cs:
            node.add_child(tree.node(c))

    for node in tree.sorted_nodes():
        print(node)


if __name__ == '__main__':
    run()

Solution (Python):
n = int(input())
rt = {}
cs = [0 for i in range(n)]
for i in range(n):
    id, k, *c = list(map(int, input().split()))
    for j in c:
        rt[j] = id
    cs[id] = c

for i in range(n):
    print("node " + str(i) + ": parent = ", end = "")
    p = [i]
    while True:
        try:
            p.append(rt[p[-1]])
        except:
            break
    if len(p) == 1:
        print("-1, depth = 0, root, ", end = "")
        print(cs[i])
    else:
        print(str(p[1]) + ", depth = " + str(len(p) - 1), end = "")
        if cs[i] == []:
            print(", leaf, []")
        else:
            print(", internal node, ",end = "")
            print(cs[i])