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):
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):
class Node():
    def __init__(self, parent =None ,left =None ,right = None):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = -1

def get_depth(u,tree_list):
    d = 0
    while tree_list[u].parent != -1:
        u = tree_list[u].parent
        d += 1
    return d

if __name__ == "__main__":
    n = int(input())

    r = 0
    tree_list = [Node(-1,-1,-1) for m in range(n)]
    node_list = []
    for i in range(n):
        l = input().split()
        v = int(l[0])
        c_list = [int(l[m]) for m in range(2,len(l))]
        node_list.insert(v,c_list)
        for ci in range(int(l[1])):
            if ci == 0:
                tree_list[v].left = c_list[ci]
            else:
                tree_list[c].right = c_list[ci]
            c = c_list[ci]
            tree_list[c].parent = v

    for i,t in enumerate(tree_list):
        d = get_depth(i,tree_list)
        tree_type = ''
        if tree_list[i].parent == -1:
            tree_type = 'root'
        elif tree_list[i].left == -1:
            tree_type = 'leaf'
        else:
            tree_type = 'internal node'

        n = ', '.join([str(x) for x in node_list[i]])

        print('node {}: parent = {}, depth = {}, {}, [{}]'.format(i,t.parent,d,tree_type,n))

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])

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])

Solution (Python):
def depth(id):
    depth = 0
    target_id = id
    while nodes[target_id][0] !=-1:
        depth += 1
        target_id = nodes[target_id][0]
    return depth

nodes = dict()
n = int(input())
for _ in range(n):
    id,k,*c_list = list(map(int, input().split()))
    if id not in nodes:
        nodes[id] = (-1, list())
    node = nodes[id]
    node = (node[0], c_list)
    nodes[id] = node
    for child_id in c_list:
        if child_id not in nodes:
            nodes[child_id] = (-1, list())
        child_node = nodes[child_id]
        child_node = (id, child_node[1])
        nodes[child_id] = child_node

for id, node in sorted(nodes.items()):
    node_type = "root" if node[0] == -1 else "internal node" if node[1] else "leaf"
    print(f"node {id}: parent = {node[0]}, depth = {depth(id)}, {node_type}, {node[1]}")

Solution (Python):
class tree:
    def __init__(self, parts):
        self.num_parts = len(parts)
        self.nodes = []
        for i in range(self.num_parts):
            self.nodes.append(node(parts[i][0],parts[i][1],parts[i][2]))

    def set_parents(self):
        for i in range(self.num_parts):
            for child_id in self.nodes[i].children_id:
                self.nodes[child_id].set_parent(i)

    def set_type(self):
        for i in range(self.num_parts):
            self.nodes[i].check_type()
    def set_depth(self):
        for i in range(self.num_parts):
            if self.nodes[i].type == "root":
                parents = [self.nodes[i]]
                depth = 0
                self.nodes[i].set_depth(depth)
                for j in range(20):
                    depth += 1
                    children = []
                    for parent in parents:
                        for child_id in parent.children_id:
                            self.nodes[child_id].set_depth(depth)
                            children.append(self.nodes[child_id])
                    parents = children
                        
class node:
    def __init__(self, id, k, children):
        self.id = id
        self.k = k
        self.children_id = children
        self.depth = -1
        self.parent_id = -1
        self.type = "leaf"
        
    def set_parent(self,parent_id):
        self.parent_id = parent_id

    def check_type(self):
        if self.parent_id == -1:
            self.type = "root"
        elif self.children_id == []:
            self.type = "leaf"
        else:
            self.type = "internal node"
            
    def set_depth(self,depth):
        self.depth = depth
        
n = int(input())
obj = [[0,0,[]] for i in range(n)]
for i in range(n):
    inp = list(map(int, input().split()))
    obj[inp[0]][0] = inp[0]
    obj[inp[0]][1] = inp[1]
    if inp[1]>0:
        obj[inp[0]][2] = inp[2:]

new_tree = tree(obj)
new_tree.set_parents()
new_tree.set_type()
new_tree.set_depth()

for i in range(n):
    print("node {}: parent = {}, depth = {}, {}, {}".format(i, new_tree.nodes[i].parent_id, new_tree.nodes[i].depth, new_tree.nodes[i].type, new_tree.nodes[i].children_id))

Solution (Python):
import sys
sys.setrecursionlimit(8388608)
N=int(input())
nodes=[None]*(N+1)
childs=[]
oya=[]
class node_tree:
    def __init__(self,node):
        self.node=node
        self.left=None
        self.right=None
        self.oya=None
for i in range(N):
    node,child_num,*child=list(map(int,input().split()))
    if nodes[node] is not None:
        parent=nodes[node]
    else:
        parent=node_tree(node)
    if child_num>=1:
        if nodes[child[0]] is not None:
            tree=nodes[child[0]]
        else:
            tree=node_tree(child[0])
        parent.left=tree
        tree.oya=parent
        nodes[node]=parent
        nodes[child[0]]=tree
        for j in range(len(child)-1):
            if nodes[child[j]] is not None:
                treesecond=nodes[child[j]]
            else:
                treesecond=node_tree(child[j])
            if nodes[child[j+1]] is not None:
                treenext = nodes[child[j+1]]
            else:
                treenext = node_tree(child[j+1])
            treesecond.oya=parent
            treenext.oya=parent
            treesecond.right=treenext
            nodes[child[j]]=treesecond
            nodes[child[j+1]]=treenext
    else:
        parent.left=nodes[-1]
        nodes[node]=parent
def oyasearch(u):
    if u.oya is not None:
        oyasearch(u.oya)
    else:
        oya.append(u.node)
oyasearch(nodes[0])
dep=[0]*N
parent_list=[None]*N
parent_list[oya[0]]=-1
child_list=[]
def search_depth(u,p):
    dep[u.node]=p
    if u.right is not None:
        parent_list[u.right.node]=parent_list[u.node]
        search_depth(u.right,p)
    if u.left is not None:
        parent_list[u.left.node]=u.node
        search_depth(u.left,p+1)
search_depth(nodes[oya[0]],0)
def child_search(u,c):
    c.append(u.node)
    if u.right is not None:
        child_search(u.right,c)
for i in range(N):
    c=[]
    if nodes[i].left is not None:
        child_search(nodes[i].left,c)
    child_list.append(c)
word_list=["internal node","leaf"]
for i in range(N):
    if i==oya[0]:
        print(("node %d: parent = %d, depth = %d, root," % (nodes[oya[0]].node, parent_list[oya[0]], dep[oya[0]])),
              child_list[oya[0]])
    else:
        if len(child_list[i])!=0:
            word=word_list[0]
        else:word=word_list[1]
        print(("node %d: parent = %d, depth = %d, %s," % (nodes[i].node, parent_list[i], dep[i],word)), child_list[i])

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

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

def cal_depth (node,x):
    node.depth = x

    for children_id in node.children:
        cal_depth(nodes[children_id],x+1)


nodes = []
for i in range(n):
    nodes.append(Node())

for i in range(n):
    table = list(map(int,input().split()))
    node_id = table[0]
    num = table[1]

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


for node in nodes:
    if node.parent_id == -1:
        cal_depth(node,0)
        break

for i in range(n):

    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):

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

global nodes

V = int(input())


nodes = []
for _ in range(V):
    node = Node()
    nodes.append(node)


for _ 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


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)

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())
root = {}
children = [0] * n

for i in range(n):
  id, k, *c = list(map(int, input().split()))
  for j in c:
    root[j] = id
  children[id] = c

for i in range(n):
  print('node {}: parent = '.format(str(i)), end='')
  p = [i]
  while True:
    try:
      p.append(root[p[-1]])
    except:
      break
  if len(p) == 1:
    print('-1, depth = 0, root, {}'.format(children[i]))
  else:
    print('{}, depth = {}'.format(str(p[1]), str(len(p) - 1)), end='')
    if children[i] == []:
      print(', leaf, []')
    else:
      print(', internal node, {}'.format(children[i]))

Solution (Python):
import sys
sys.setrecursionlimit(100010)
n=int(input())
childs_list=[[] for _ in range(n)]
for i in range(n):
    tmp=list(map(int, input().split()))
    childs_num=tmp[1]
    node_id=tmp[0]
    childs_list[node_id].extend(tmp[2:])

class Tree:
    def __init__(self,childs_list):
        self.n=len(childs_list)
        self.parent=[-1]*self.n
        self.first_child=[-1]*self.n
        self.next_child=[-1]*self.n
        for i in range(self.n):
            childs_num=len(childs_list[i])
            if childs_num == 0:
                continue
            self.first_child[i]=childs_list[i][0]
            for j in range(childs_num):
                self.parent[childs_list[i][j]]=i
                if j < childs_num-1:
                    self.next_child[childs_list[i][j]]=childs_list[i][j+1]
        self.node_type=[0]*n
        for i in range(self.n):
            if self.parent[i]==-1:
                self.node_type[i]="root"
                self.root=i
            elif self.first_child[i]==-1:
                self.node_type[i]="leaf"
            else:
                self.node_type[i]="internal node"
        self.d=[-1]*self.n

    def parent_of(self,id):
        return self.parent[id]
    
    def childs_of(self,id):
        childs=[]
        if self.first_child[id]==-1:
            return childs
        else:
            now_child=self.first_child[id]
            while 1:
                childs.append(now_child)
                if self.next_child[now_child] == -1:
                    break
                else:
                    now_child=self.next_child[now_child]
        return childs
    
    def set_depth(self,id,d):
        if id != -1:
            self.d[id]=d
            self.set_depth(self.next_child[id],d)
            self.set_depth(self.first_child[id],d+1)


tree=Tree(childs_list)
tree.set_depth(tree.root,0)

for i in range(n):
    print("node {}: ".format(i),end="")
    print("parent = {}, ".format(tree.parent_of(i)),end="")
    print("depth = {}, ".format(tree.d[i]),end="")
    print("{}, ".format(tree.node_type[i]),end="")
    print(tree.childs_of(i))

Solution (Python):
n = int(input())
parent = [-1 for i in range(n)]
depth = [-1 for i in range(n)]
G = [[] for i in range(n)]
for _ in range(n):
    cin = input().split()
    id, k = int(cin[0]), int(cin[1])
    children = list(map(int, cin[2:]))
    G[id] = children
    for child in children:
        parent[child] = id
for i in range(n):
    if parent[i] == -1:
        depth[i] = 0
        que = [i]
        while len(que) > 0:
            r = que.pop()
            for child in G[r]:
                depth[child] = depth[r] + 1
                que.append(child)
        break
for i in range(n):
    T = ''
    if parent[i] == -1:
        T = 'root'
    elif len(G[i]) == 0:
        T = 'leaf'
    else:
        T = 'internal node'
    print(f'node {i}: parent = {parent[i]}, depth = {depth[i]}, {T}, {G[i]}')

Solution (Python):
class Node:
    def __init__(self, p, l, r):
        self.p, self.l, self.r = p, l, r

N = int(input())
T = [Node(None, None, None) for _ in range(N)]

def get_depth(i):
    depth = 0
    while T[i].p != None:
        depth += 1
        i = T[i].p
    return depth

def get_children(i):
    children = []
    child = T[i].l
    while child != None:
        children.append(child)
        child = T[child].r
    return children

for _ in range(N):
    node, num, *children = map(int, input().split())
    if len(children) > 0:
        T[node].l = children[0]
        for i, child in enumerate(children):
            if len(children) - 1 < i + 1:
                break
            T[child].r = children[i + 1]
        for child in children:
            T[child].p = node

for i, t in enumerate(T):
    parent = t.p if t.p != None else -1
    depth = get_depth(i)
    if t.p == None:
        node = 'root'
    elif t.l == None:
        node = 'leaf'
    else:
        node = 'internal node'
    children = get_children(i)
    print('node {}:'.format(i), end=' ')
    print('parent = {},'.format(parent), end=' ')
    print('depth = {},'.format(depth), end=' ')
    print('{},'.format(node), end=' ')
    print(children)

Solution (Python):
class Node():
    def __init__(self, value, parent=None):
        self.value = value
        self.parent = parent
        self.left_child = None
        self.right_sibling = None

    def set_left_child(self, child):
        self.left_child = child

    def set_right_sibling(self, sibling):
        self.right_sibling = sibling

    def set_parent(self, parent):
        self.parent = parent

    def get_depth(self):
        if self.parent is None:
            return 0

        return self.parent.get_depth() + 1

    def get_childs(self):
        r = []
        child = self.left_child
        while child is not None:
            r.append(child.value)
            child = child.right_sibling
        return r

    def print(self):
        childs = self.get_childs()
        depth = self.get_depth()
        p = str(self.parent.value if self.parent else -1)
        t = 'leaf'
        if self.parent is None:
            t = 'root'
        elif childs and self.parent:
            t = 'internal node'

        print('node ' + str(self.value) + ': parent = ' + p + ', depth = ' + str(depth) + ', ' + t + ', ' + str(childs))


n = int(input())
m = {}
for _ in range(n):
    l = list(map(int, input().split()))
    p = m[l[0]] if m.get(l[0]) else Node(l[0])
    if l[1] >= 1:
        sibling = None
        for i in range(2, 2 + l[1])[::-1]:
            node = m[l[i]] if m.get(l[i]) else Node(l[i])
            node.right_sibling = sibling
            node.parent = p
            sibling = node
            m[node.value] = node
        p.left_child = node
    m[l[0]] = p

for i in range(n):
    m[i].print()

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


NIL = -1

n = int(input())


class Node:
    def __init__(self, p, l, r):
        self.p = p
        self.l = l
        self.r = r
        self.d = 0
        self.t = 'undifined'
        self.c = []


T = [Node(NIL, NIL, NIL) for _ in range(n)]


for _ in range(n):
    data = [int(i) for i in input().split()]
    node_id = data[0]
    node_d = data[1]
    child = data[2:]
    if len(child) > 0:
        T[node_id].l = child[0]
    for i in range(len(child)):
        if i < len(child)-1:
            T[child[i]].r = child[i+1]
        T[child[i]].p = node_id
        T[node_id].c.append(child[i])







def setDepth(root_id, depth):
    T[root_id].d = depth
    l = T[root_id].l
    r = T[root_id].r
    if l != NIL:
        setDepth(l, depth+1)
    if r != NIL:
        setDepth(r, depth)


def getRoot():
    for i in range(n):
        p = T[i].p
        if p == NIL:
            return i


def setNodeType(node_id):
    
    if T[node_id].p == NIL:
        T[node_id].t = 'root'
        return
    
    if T[node_id].l == NIL:
        T[node_id].t = 'leaf'
        return 
    
    T[node_id].t = 'internal node'

def allSetNodeType():
    for i in range(n):
        setNodeType(i)

def outPutNodeInfo(node_id, p_node_id, depth='nil', node_type='nil', child_list='nil'):
    res = "node {}: parent = {}, depth = {}, {}, {}".format(node_id, p_node_id, depth, node_type, child_list)
    print(res)



def outPutAns():
    for i in range(n):
        node_id = i
        p_node_id = T[i].p
        depth = T[i].d
        node_type = T[i].t
        child_list = T[i].c
        outPutNodeInfo(node_id, p_node_id, depth, node_type, child_list)



def main():
    setDepth(getRoot(), 0)
    allSetNodeType()
    outPutAns()
main()

Solution (Python):
class Node:
    def __init__(self,parent = -1,childs = []):
        self.p = parent
        self.c = childs


def main():
    n = int(input())
    t = [Node() for _ in range(n)]
    for i in range(n):
        b = list(map(int,input().split()))
        t[b[0]].c = b[2:]
        for d in b[2:]:t[d].p = b[0]

    def depth(i):
        res = 0
        while t[i].p!=-1:
            i = t[i].p
            res+=1
        return res

    for i in range(n):
        print('node %d: parent = %d, '%(i,t[i].p),end='')
        print('depth = %d, '%depth(i),end='')
        if t[i].p==-1      :print ('root,',t[i].c)
        elif len(t[i].c)!=0:print ('internal node,',t[i].c)
        else               :print ('leaf,',t[i].c)

if __name__ == '__main__':
    main()

Solution (Python):
NIL = -1


class Node():
  def __init__(self, nid):
    self.nid = nid
    self.parent = -1
    self.left = self.right = None
    self.depth = None

  def __str__(self):

    template = "node {}: parent = {}, depth = {}, {}, {}"
    if self.parent == -1:
      ntype = "root"
    elif self.left is None:
      ntype = "leaf"
    else:
      ntype = "internal node"

    children = self.get_childs()
    chidlren = ", ".join(map(str,children))
    parend_id = self.parent.nid if self.parent != -1 else -1
    return template.format(
      self.nid, parend_id, self.depth, ntype, children
    )
  
  def get_childs(self):
    c = self.left
    children = []
    while c is not None:
      children.append(c.nid)
      c = c.right
    return children
  
      


def set_depth(node, p):
  node.depth = p
  if node.right is not None:
    set_depth(node.right, p)
  if node.left is not None:
    set_depth(node.left, p+1)

def main():
  n = int(input())
  T = [Node(i) for i in range(n)]
  for i in range(n):
    tmp = list(map(int, input().split()))
    nid = tmp[0]
    k = tmp[1]
    c = tmp[2:]
    if len(c) == 0:
      continue
    T[nid].left = T[c[0]]
    for idx in c:
      T[idx].parent = T[nid]
    for j in range(k-1):
      T[c[j]].right = T[c[j+1]]
  for i in range(n):
    if T[i].parent == -1:
      break
  set_depth(T[i], 0)
  for x in T:
    print(x)



if __name__ == "__main__":
    import io, sys
    sys.setrecursionlimit(200000)
    main()

Solution (Python):
import sys
sys.setrecursionlimit(2 ** 20)

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

    def __repr__(self):
        return '<Node object: parent={}, left={}, right={}>' .format(self.parent, self.left, self.right)


def set_depth(u, p):
    D[u] = p
    if not T[u].right is None:
        set_depth(T[u].right, p)
    if not T[u].left is None:
        set_depth(T[u].left, p+1)


def get_children(u):
    res = []
    c = T[u].left
    while c is not None:
        res.append(c)
        c = T[c].right
    return res


def get_type(node):
    if node.parent is None:
        return 'root'
    elif node.left is None:
        return 'leaf'
    else:
        return 'internal node'


def get_parent(node):
    return -1 if node.parent is None else node.parent


n = int(input())
T = [Node() for i in range(n)]
for _ in range(n):
    line = list(map(int, input().split()))
    i, k = line[:2]
    if k:
        T[i].left = line[2]
        prev = None
        for c in line[2:]:
            T[c].parent = i
            if prev:
                T[prev].right = c
            prev = c

D = [0] * n
for i in range(n):
    if T[i].parent is None:
        set_depth(i, 0)
        break

for i in range(n):
    print('node {}: parent = {}, depth = {}, {}, {}'.format(
        i, get_parent(T[i]), D[i], get_type(T[i]), get_children(i)))

Solution (Python):
import sys
sys.setrecursionlimit(2**20)
n = int(input())
NIL = -1
class node:
    def __init__(self,parent,left,right):
        self.parent = parent
        self.left = left
        self.right = right
T = [node(NIL,NIL,NIL) for _ in range(n)]
firstid = 0
for _ in range(n):
    A = list(map(int,input().split()))
    id = A[0]
    if n == 1:
        firstid = id
    k = A[1]
    if k != 0:
        chil = A[2:2+k]
        T[id].left = chil[0]
        for i in range(k):
            if i != k-1:
                T[chil[i]].right = chil[i+1]
                T[chil[i]].parent = id
            else:
                T[chil[i]].parent = id            
D = [0]*n
def setDepth(u,p):
    D[u] = p      
    if T[u].right != NIL:
        setDepth(T[u].right,p)
    if T[u].left != NIL:
        setDepth(T[u].left,p+1)
    return D
def getDepth(u):
    d = 0
    while T[u].parent != NIL:
        u = T[u].parent
        d += 1
    return d
def findroot(u): 
    while T[u].parent != NIL:
        u = T[u].parent
    return u
def printChildren(u):
    child = []
    if T[u].left != NIL:
        c = T[u].left
        while c != NIL:
            child.append(c)
            c = T[c].right
    return child
def ppp():
	for i in range(n):
  		ccc = T[i]
  		print(i,ccc.parent,ccc.left,ccc.right)

r = findroot(firstid)
D = setDepth(r,0)
for i in range(n):
    nod = T[i]
    d = getDepth(i)
    s = "internal node"
    if nod.parent == NIL:
        s = "root"
    elif nod.left == NIL:
        s = "leaf"
    child = printChildren(i)
    print(f'node {i}: parent = {nod.parent}, depth = {d}, {s}, {child}')

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

class Node:
    def __init__(self):
        self.p = -1
        self.l = -1
        self.r = -1

n = int(input())
T = [Node() for _ in range(n)]
D = [0]*n

def rec(u,p):
    D[u] = p
    if T[u].r != -1: rec(T[u].r,p)
    if T[u].l != -1: rec(T[u].l,p+1)

def printinfo(u):
    clst = []
    c = T[u].l
    while c != -1:
        clst.append(c)
        c = T[c].r
    if T[u].p == -1: ntype = "root"
    elif T[u].l == -1: ntype = "leaf"
    else: ntype = "internal node"
    print("node {}: parent = {}, depth = {}, {}, {}".format(u,T[u].p,D[u],ntype,clst))

for i in range(n):
    inp = [int(i) for i in input().split()]
    v = inp[0]
    d = inp[1]
    C = inp[2:]
    for j in range(d):
        c = C[j]
        if j == 0: T[v].l = c
        else: T[l].r = c
        l = c
        T[c].p = v
for i in range(n):
    if T[i].p == -1: r = i

rec(r,0)
for i in range(n): printinfo(i)

Solution (Python):
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("]")