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):
def Get_leafs_list(T, p):
    l = p.l
    ans = []
    while(T[l].r != -1):
        ans.append(T[l].r)
        l = T[l].r
    return ans

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


class Node():
    def __init__(self,i):
        self.p = -1
        self.l = -1
        self.r = -1
        self.d = 0
        self.n = i

    def Get_leafs_list(self,T):
        l = self.l
        if l != -1:
            ans = [l]
        else:
            ans = []
        while(T[l].r != -1):
            ans.append(T[l].r)
            l = T[l].r
        return ans


    def print_ans(self):
        print("node",self.n, end=": ")
        print("parent =",self.p, end=", ")
        print('depth =',self.d, end=", ")
        if self.l == -1 and self.p != -1:
            print('leaf, []')
            return
        else:
            if self.p == -1:
                print("root",end=", ")
            else :
                print("internal node",end=", ")
            ans = self.Get_leafs_list(T)
            print(ans)
T = []
n = int(input())
for i in range(0,n):
    T.append(Node(i))

for i in range(0,n):
    data = [int(x) for x in input().split()]
    k = data[0]
    if(data[1] != 0):   
        for j in range(0,data[1]):  
            if j == 0:
                T[k].l = data[2]
            else:
                T[l].r = data[2+j]
            l = data[2+j]
            T[l].p = data[0]

for x in range(0,n):
    if(T[x].p == -1):
        root = x
        break
try:
    rec(T,root,0)

except:
    for i in range(1,n):
        T[i].d = 1

for x in T:
    x.print_ans()

Solution (Python):
class Node:
    def __init__(self):
        self.parent = -1


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


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

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

    def get_type(self):
        if self.parent == -1: return "root"
        elif self.left == -1: return "leaf"
        else: return "internal node"

def set_depth(u,d):
    global D
    global tree
    D[u] = d
    v = tree[u].right
    while not v == -1:
        D[v] = d
        if not tree[v].left == -1:
            set_depth(tree[v].left, d+1)
        v = tree[v].right
    if not tree[u].left == -1:
        set_depth(tree[u].left, d+1)

def print_tree(t,D):
    for i in range(len(t)):
        children = []
        c = t[i].left
        if not c == -1:
            while True:
                children.append(c)
                c = t[c].right
                if c == -1: break
        print "node %s: parent = %s, depth = %s, %s, [%s]" % (i, t[i].parent, D[i], t[i].get_type(), ", ".join(map(str, children)))

n = int(raw_input().strip())

tree = {}
for i in range(n):
    tree[i] = Node(-1, -1, -1)
for _ in range(n):
    entry = map(int, raw_input().strip().split(' '))
    nid = entry[0]
    n_child = entry[1]
    for i in range(n_child):
        if i == 0: tree[nid].left = entry[i+2]
        else: tree[entry[i+1]].right = entry[i+2]
        tree[entry[i+2]].parent = nid

r = -1
for i in range(n):
    if tree[i].parent == -1: r = i

D = {}
set_depth(r, 0)

print_tree(tree, D)

Solution (Python):


class Node():
    def __init__(self, node_id, children):
        self.node_id = node_id
        self.parent = -1
        self.depth = 0
        self.typ = "root"
        self.children = children

    def set_child(self, child):
        """ Overwrite child's attribute """
        child.parent = self.node_id
        child.depth = self.depth + 1
        if child.children:
            child.typ = "internal node"
        else:
            child.typ = "leaf"

    def set_children(self, tree):
        """ Repeat set_child starting from root node """
        stack = []
        stack.append(self.node_id)

        while stack:
            node = tree[stack.pop()]
            for child_id in node.children:
                node.set_child(tree[child_id])
            stack.extend(node.children)

n = int(input())
tree = [None for i in range(n)]
children = []
for i in range(n):
    info = list(map(int, input().split()))
    tree[info[0]] = Node(info[0], info[2:])
    children.extend(info[2:])

root_id = list(set([x for x in range(n)]) - set(children)).pop()

tree[root_id].set_children(tree)

for node in tree:
    print("node {}: parent = {}, depth = {}, {}, {}".format(node.node_id, node.parent, node.depth, node.typ, node.children))

Solution (Python):


class Node():
    def __init__(self, node_id, children):
        self.node_id = node_id
        self.parent = -1
        self.depth = 0
        self.typ = "root"
        self.children = children

    def set_child(self, child):
        """ Overwrite child's attribute """
        child.parent = self.node_id
        child.depth = self.depth + 1
        if child.children:
            child.typ = "internal node"
        else:
            child.typ = "leaf"

    def set_children(self, tree):
        """ Repeat set_child starting from root node """
        stack = []
        stack.append(self.node_id)

        while stack:
            node = tree[stack.pop()]
            for child_id in node.children:
                node.set_child(tree[child_id])
            stack.extend(node.children)

n = int(input())
tree = [None for i in range(n)]
children = []
for i in range(n):
    info = list(map(int, input().split()))
    tree[info[0]] = Node(info[0], info[2:])
    children.extend(info[2:])

root_id = (set([x for x in range(n)]) - set(children)).pop()

tree[root_id].set_children(tree)

for node in tree:
    print("node {}: parent = {}, depth = {}, {}, {}".format(node.node_id, node.parent, node.depth, node.typ, node.children))

Solution (Python):


class Node():
    def __init__(self, node_id, children):
        self.node_id = node_id
        self.parent = -1
        self.depth = 0
        self.typ = "root"
        self.children = children

    def set_child(self, child):
        """ Overwrite child's attribute """
        child.parent = self.node_id
        child.depth = self.depth + 1
        if child.children:
            child.typ = "internal node"
        else:
            child.typ = "leaf"

    def set_children(self, tree):
        """ Repeat set_child starting from root node """
        stack = []
        stack.append(self.node_id)

        while stack:
            node = tree[stack.pop()]
            for child_id in node.children:
                node.set_child(tree[child_id])
            stack.extend(node.children)

n = int(input())
tree = [None for i in range(n)]
children = []
for i in range(n):
    info = list(map(int, input().split()))
    tree[info[0]] = Node(info[0], info[2:])
    children.extend(info[2:])

root_id = (set([x for x in range(n)]) - set(children)).pop()

tree[root_id].set_children(tree)

for node in tree:
    print("node {}: parent = {}, depth = {}, {}, {}".format(node.node_id, node.parent, node.depth, node.typ, node.children))

Solution (Python):
n = int(input())
tree = [None] * n
root = set(range(n))


def set_pd(i, parent, depth):
    node = tree[i]
    node[1], node[2] = parent, depth
    for child in node[0]:
        set_pd(child, i, depth + 1)


while n:
    l = list(map(int, input().split()))
    c = l[2:]
    tree[l[0]] = [c, None, None]
    root -= set(c)
    n -= 1

set_pd(root.pop(), -1, 0)

for i, node in enumerate(tree):
    c, p, d = node
    print('node {}: parent = {}, depth = {}, {}, [{}]'.format(
        i, p, d, 'root' if not d else 'internal node' if c else 'leaf', ', '.join(map(str, c))
    ))

Solution (Python):


class Node():
    def __init__(self, node_id, degree, children):
        self.node_id    =   node_id
        self.parent     =   -1
        self.depth      =   0
        self.typ        =   "leaf"
        self.degree     =   degree
        self.children   =   children

    def set_attr(self, parent, depth):
        self.parent =   parent
        self.depth  =   depth
        for child_id in self.children:
            self.typ = "internal node"
            tree[child_id].set_attr(self.node_id, self.depth + 1)
        if self.parent == -1:
            self.typ = "root"

n = int(input())
tree = [None for i in range(n)]
root = set(range(n))

for i in range(n):
    info = list(map(int, input().split()))
    tree[info[0]] = Node(info[0], info[1], info[2:])
    root -= set(info[2:])

root_id = root.pop()
tree[root_id].set_attr(-1, 0)

for node in tree:
    print("node {}: parent = {}, depth = {}, {}, {}".format(node.node_id, node.parent, node.depth, node.typ, node.children))

Solution (Python):


class Node():
    def __init__(self, node_id, degree, children):
        self.node_id    =   node_id
        self.parent     =   -1
        self.depth      =   0
        self.typ        =   "leaf"
        self.degree     =   degree
        self.children   =   children

    def set_attr(self, parent, depth):
        self.parent =   parent
        self.depth  =   depth
        for child_id in self.children:
            self.typ = "internal node"
            tree[child_id].set_attr(self.node_id, self.depth + 1)
        if self.parent == -1:
            self.typ = "root"

n = int(input())
tree = [None for i in range(n)]
root = set(range(n))

for i in range(n):
    info = list(map(int, input().split()))
    tree[info[0]] = Node(info[0], info[1], info[2:])
    root -= set(info[2:])

root_id = root.pop()
tree[root_id].set_attr(-1, 0)

for node in tree:
    print("node {}: parent = {}, depth = {}, {}, {}".format(node.node_id, node.parent, node.depth, node.typ, node.children))

Solution (Python):


class Node():
    def __init__(self, node_id, children):
        self.node_id    =   node_id
        self.parent     =   -1
        self.depth      =   0
        self.typ        =   "leaf"
        self.children   =   children

    def set_attr(self, parent, depth):
        self.parent =   parent
        self.depth  =   depth
        for child_id in self.children:
            self.typ = "internal node"
            tree[child_id].set_attr(self.node_id, self.depth + 1)
        if self.parent == -1:
            self.typ = "root"

n = int(input())
tree = [None for i in range(n)]
root = set(range(n))

for i in range(n):
    info = list(map(int, input().split()))
    tree[info[0]] = Node(info[0], info[2:])
    root -= set(info[2:])

root_id = root.pop()
tree[root_id].set_attr(-1, 0)

for node in tree:
    print("node {}: parent = {}, depth = {}, {}, {}".format(node.node_id, node.parent, node.depth, node.typ, node.children))

Solution (Python):

from __future__ import division, print_function
from sys import stdin
 
FORMAT = ('node {0.id}: parent = {0.parent}, depth = {0.depth},'
          ' {0.kind}, {0.childs}').format
 
 
class Node(object):
    def __init__(self, node):
        self.depth = 0
        self.parent = -1
        self.id = node[0]
        self.degree = node[1]
        self.kind = 'internal node' if node[1] else 'leaf'
        self.childs = node[2:]
 
    def __str__(self):
        return FORMAT(self)
 
 
def calc_depth(tree, i):
    for j in tree[i].childs:
        tree[j].depth += 1
        calc_depth(tree, j)
 
 
n = int(stdin.readline())
tree = [-1] * n

for _ in xrange(n):
    node = Node([int(s) for s in stdin.readline().split()])
    i = node.id
    node.parent = tree[i]
    for j in node.childs:
        if isinstance(tree[j], int):
            tree[j] = i
        else:
            tree[j].parent = i
    tree[i] = node
 
for i in xrange(n):
    calc_depth(tree, i)
 
for i, node in enumerate(tree):
    if node.parent == -1:
        node.kind = 'root'
    print(node)

Solution (Python):
class Node:
    def __init__(self, num, parent, leftmostChild, rightSibling):
        self.id = num
        self.parent = parent
        self.leftmostChild = leftmostChild
        self.rightSibling = rightSibling
        self.depth = 0
        
    def show_info(self):
        print('node {0}: '.format(self.id), end = '')
        print('parent = {0}, '.format(self.parent.id), end = '')
        print('depth = {0}, '.format(self.depth), end = '')
        if self.leftmostChild and self.parent.id != -1:
            print('internal node, ', end = '')
        elif self.parent.id != -1:
            print('leaf, ', end = '')
        else:
            print('root, ', end = '')
        print('[', end = '')
        t_n = self.leftmostChild
        if t_n:
            print(t_n.id, end = '')
            t_n = t_n.rightSibling
        while t_n:
            print(', {0}'.format(t_n.id), end = '')
            t_n = t_n.rightSibling
        print(']')


class RootedTree():
    def __init__(self, n):
        self.base_node = Node(-1, None, None, None)
        self.nodes = [Node(i, self.base_node, None, None) for i in range(n)]
    
    def set_node(self, num, k, *children):
        if children:
            self.nodes[num].leftmostChild = self.nodes[children[0]]
            for i, x in enumerate(children[:-1]):
                self.nodes[x].parent = self.nodes[num]
                self.nodes[x].rightSibling = self.nodes[children[i + 1]]
            self.nodes[children[-1]].parent = self.nodes[num]

    def set_depth(self):
        for n in self.nodes:
            t_n = n
            while t_n.parent.id != -1:
                n.depth += 1
                t_n = t_n.parent

    def show_nodes_info(self):
        for n in self.nodes:
            n.show_info()



import sys

n = int(sys.stdin.readline())

T = RootedTree(n)

for x in sys.stdin.readlines():
    T.set_node(*list(map(int, x.split())))

T.set_depth()

T.show_nodes_info()

Solution (Python):
"""Rooted Trees."""

class Node:
    def __init__(self, num, parent, *children):
        self.id = num
        self.parent = parent
        self.children = list(children)
        self.depth = 0
        
    def show_info(self):
        print('node {0}: '.format(self.id), end = '')
        print('parent = {0}, '.format(self.parent), end = '')
        print('depth = {0}, '.format(self.depth), end = '')
        if self.children and self.parent != -1:
            print('internal node, ', end = '')
        elif self.parent != -1:
            print('leaf, ', end = '')
        else:
            print('root, ', end = '')
        print(self.children)


class RootedTree():
    def __init__(self, n):
        self.nodes = [Node(i, -1) for i in range(n)]
    
    def set_node(self, i_p):
        i_p = list(map(int, i_p.split()))
        num = i_p[0]
        children = i_p[2:]
        if children:
            self.nodes[num].children = children
            for n in children:
                self.nodes[n].parent = num

    def set_depth(self):
        for n in self.nodes:
            t_n = n
            while t_n.parent != -1:
                n.depth += 1
                t_n = self.nodes[t_n.parent]

    def show_nodes_info(self):
        for n in self.nodes:
            n.show_info()



import sys

n = int(sys.stdin.readline())

T = RootedTree(n)

for x in sys.stdin.readlines():
    T.set_node(x)

T.set_depth()

T.show_nodes_info()

Solution (Python):
class Node:
    def __init__(self, num, parent, *children):
        self.id = num
        self.parent = parent
        self.children = list(children)
        self.depth = 0
        
    def show_info(self):
        print('node {0}: '.format(self.id), end = '')
        print('parent = {0}, '.format(self.parent), end = '')
        print('depth = {0}, '.format(self.depth), end = '')
        if self.children and self.parent != -1:
            print('internal node, ', end = '')
        elif self.parent != -1:
            print('leaf, ', end = '')
        else:
            print('root, ', end = '')
        print(self.children)


def set_node(i_p):
    i_p = list(map(int, i_p.split()))
    num = i_p[0]
    children = i_p[2:]
    if children:
        T[num].children = children
        for n in children:
            T[n].parent = num

def find_root(node):
    while node.parent != -1:
        node = T[node.parent]
    return node

def set_depth(node, depth):
    node.depth = depth
    for n in node.children:
        set_depth(T[n], depth + 1)



import sys

n = int(sys.stdin.readline())

T = [Node(i, -1) for i in range(n)]

for x in sys.stdin.readlines():
    set_node(x)

r_n = find_root(T[0])

set_depth(r_n, 0)

for n in T:
    n.show_info()

Solution (Python):
class Node:
    def __init__(self, num, parent, children):
        self.id = num
        self.parent = -1
        self.children = children
        self.depth = 0
        
    def show_info(self):
        print('node {0}: '.format(self.id), end = '')
        print('parent = {0}, '.format(self.parent), end = '')
        print('depth = {0}, '.format(self.depth), end = '')
        if self.children and self.parent != -1:
            print('internal node, ', end = '')
        elif self.parent != -1:
            print('leaf, ', end = '')
        else:
            print('root, ', end = '')
        print(self.children)


def set_node(i_s):
    i_l = list(map(int, i_s.split()))
    num = i_l[0]
    children = i_l[2:]
    node = Node(num, -1, children)
    T[num] = node
    for n in children:
        rn_check_list.remove(n)

def set_pd(node, parent, depth):
    node.parent = parent
    node.depth = depth
    for n in node.children:
        set_pd(T[n], node.id, depth + 1)


import sys

n = int(sys.stdin.readline())

T = [None for i in range(n)]

rn_check_list = [i for i in range(n)]

for x in sys.stdin.readlines():
    set_node(x)

rn_i = rn_check_list[0]

set_pd(T[rn_i], -1, 0)

for n in T:
    n.show_info()

Solution (Python):
class Node:
    def __init__(self, num, parent, children):
        self.id = num
        self.parent = -1
        self.children = children
        self.depth = 0
        
    def show_info(self):
        print('node {0}: '.format(self.id), end = '')
        print('parent = {0}, '.format(self.parent), end = '')
        print('depth = {0}, '.format(self.depth), end = '')
        if self.children and self.parent != -1:
            print('internal node, ', end = '')
        elif self.parent != -1:
            print('leaf, ', end = '')
        else:
            print('root, ', end = '')
        print(self.children)


def set_node(i_s):
    i_l = list(map(int, i_s.split()))
    num = i_l[0]
    children = i_l[2:]
    node = Node(num, -1, children)
    T[num] = node
    for n in children:
        T[-1] -= n

def set_pd(node, parent, depth):
    node.parent = parent
    node.depth = depth
    for n in node.children:
        set_pd(T[n], node.id, depth + 1)


import sys

n = int(sys.stdin.readline())

T = [None for i in range(n)]

T.append(int(n * (n - 1) / 2))

for x in sys.stdin.readlines():
    set_node(x)

set_pd(T[T[-1]], -1, 0)

for n in T[:-1]:
    n.show_info()

Solution (Python):
class Node:
    def __init__(self, num, parent, children):
        self.id = num
        self.parent = -1
        self.children = children
        self.depth = 0
        
    def show_info(self):
        print('node {0}: '.format(self.id), end = '')
        print('parent = {0}, '.format(self.parent), end = '')
        print('depth = {0}, '.format(self.depth), end = '')
        if self.children and self.parent != -1:
            print('internal node, ', end = '')
        elif self.parent != -1:
            print('leaf, ', end = '')
        else:
            print('root, ', end = '')
        print(self.children)


def set_node(i_s):
    i_l = list(map(int, i_s.split()))
    num = i_l[0]
    children = i_l[2:]
    node = Node(num, -1, children)
    T[num] = node
    for n in children:
        T[-1] -= n

def set_pd(n_i, parent, depth):
    node = T[n_i]
    node.parent = parent
    node.depth = depth
    for n in node.children:
        set_pd(n, n_i, depth + 1)


import sys

n = int(sys.stdin.readline())

T = [None] * n

T.append(int(n * (n - 1) / 2))

for x in sys.stdin.readlines():
    set_node(x)

set_pd(T[-1], -1, 0)

for n in T[:-1]:
    n.show_info()

Solution (Python):
class Node:
    def __init__(self, num, parent, children):
        self.id = num
        self.parent = -1
        self.children = children
        self.depth = 0
        
    def show_info(self):
        print('node {0}: '.format(self.id), end = '')
        print('parent = {0}, '.format(self.parent), end = '')
        print('depth = {0}, '.format(self.depth), end = '')
        if self.children and self.parent != -1:
            print('internal node, ', end = '')
        elif self.parent != -1:
            print('leaf, ', end = '')
        else:
            print('root, ', end = '')
        print(self.children)


def set_node(i_s):
    i_l = list(map(int, i_s.split()))
    num = i_l[0]
    children = i_l[2:]
    node = Node(num, -1, children)
    T[num] = node
    for n in children:
        T[-1] -= n

def set_pd(n_i, parent, depth):
    node = T[n_i]
    node.parent = parent
    node.depth = depth
    for n in node.children:
        set_pd(n, n_i, depth + 1)


import sys

n = int(sys.stdin.readline())

T = [None] * n

T.append(int(n * (n - 1) / 2))

for x in sys.stdin.readlines():
    set_node(x)

set_pd(T[-1], -1, 0)

for n in T[:-1]:
    n.show_info()

Solution (Python):
class Node:
    def __init__(self, num, parent, children):
        self.id = num
        self.parent = -1
        self.depth = 0
        self.type = None
        self.children = children
        
    def show_info(self):
        print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(self.id,
                                                                     self.parent,
                                                                     self.depth,
                                                                     self.type,
                                                                     self.children))


def set_node(i_s):
    i_l = list(map(int, i_s.split()))
    num = i_l[0]
    children = i_l[2:]
    node = Node(num, -1, children)
    T[num] = node
    for n in children:
        T[-1] -= n

def set_pdt(n_i, parent, depth):
    node = T[n_i]
    node.parent = parent
    node.depth = depth
    if node.children:
        node.type = 'internal node'
        for n in node.children:
            set_pdt(n, n_i, depth + 1)
    else:
        node.type = 'leaf'


import sys

n = int(sys.stdin.readline())

T = [None] * n

T.append(int(n * (n - 1) / 2))

for x in sys.stdin.readlines():
    set_node(x)

set_pdt(T[-1], -1, 0)

T[T[-1]].type ='root'

for n in T[:-1]:
    n.show_info()

Solution (Python):
from collections import deque, namedtuple

class RootedTree:
    def __init__(self, t, n):
        self.t = t
        self.n = n
        self.d = [-1] * n

    def setDepth(self, u, p):
        self.t[u] = self.t[u]._replace(d = p)
        for i in self.getChildren(u):
            self.setDepth(i, p + 1)

    def getChildren(self, u):
        ret = []
        c = self.t[u].l
        while c != -1:
            ret.append(c)
            c = self.t[c].r
        return(ret)

    def printNode(self, i):
        p_ = self.t[i].p
        d_ = self.t[i].d
        c_ = self.getChildren(i)
        if p_ == -1:
            t_ = "root"
        elif len(c_) == 0:
            t_ = "leaf"
        else:
            t_ = "internal node"
        print("node {}: parent = {}, depth = {}, {}, {}".format(i, p_, d_, t_, c_))

if __name__ == '__main__':
    n = int(input().rstrip())
    Node = namedtuple('Node', ['p', 'l', 'r', 'd'])
    t = [Node(-1, -1, -1, -1)] * n
    r = -1
    for i in range(n):
        tmp = deque([int(i) for i in input().rstrip().split(" ")])
        v = tmp.popleft()
        d = tmp.popleft()
        for j in range(d):
            c = tmp.popleft()
            if j == 0:
                t[v] = t[v]._replace(l = c)
            else:
                t[l] = t[l]._replace(r = c)
            l = c
            t[c] = t[c]._replace(p = v)
    for i in range(n):
        if (t[i].p == -1):
            r = i
    x = RootedTree(t, n)
    x.setDepth(r, 0)
    for i in range(n):
        x.printNode(i)

Solution (Python):
class Tree():
    def __init__(self):
        self.parent = -1
        self.depth = 0
        self.child = []

n = int(input())
tree = [Tree() for i in range(n)]
for i in range(n):
    cmd = list(map(int, input().split()))
    node = tree[cmd[0]]
    node.child.extend(cmd[2:])
    for j in cmd[2:]:
        c = tree[j]
        c.parent = cmd[0]
for t in tree:
    d, p = 0, t.parent
    while p != -1:
        d += 1
        p = tree[p].parent
    t.depth = d
for i in range(n):
    t = tree[i]
    if t.parent == -1:
        state = 'root'
    elif t.child:
        state = 'internal node'
    else:
        state = 'leaf'
    print('node {}: parent = {}'.format(i, t.parent),
          'depth = {}'.format(t.depth),
          state,
          '[{}]'.format(', '.join(map(str, t.child))),
          sep=', ')

Solution (Python):
class Tree():

    def __init__(self):
        self.parent = -1
        self.depth = 0
        self.child = []

n = int(input())
tree = [Tree() for i in range(n)]
for i in range(n):
    cmd = list(map(int, input().split()))
    node = tree[cmd[0]]
    node.child.extend(cmd[2:])
    for j in cmd[2:]:
        tree[j].parent = cmd[0]

for t in tree:
    d, p = 0, t.parent
    while p != -1:
        d += 1
        p = tree[p].parent
    t.depth = d

for i in range(n):
    t = tree[i]
    if t.parent == -1:
        state = "root"
    elif t.child:
        state = "internal node"
    else:
        state = "leaf"
    print("node {}: parent = {}".format(i, t.parent), "depth = {}".format(
        t.depth), state, "[{}]".format(", ".join(map(str, t.child))), sep=", ")

Solution (Python):


class Node_Class():
    def __init__(self, c_list):
        self.c_list = c_list

n = int(raw_input())
node_dic = {}
p_list = [0]*n
d_list = [0]*n
t_list = ['']*n
root = 0
for i in range(n):
    root += i
for i in range(n):
    line = map(str, raw_input().split())
    if int(line[1]) > 0:
        node_dic[int(line[0])] = Node_Class(map(int, line[2:]))
    else:
        node_dic[int(line[0])] = Node_Class([])

for i in range(n):
    for j in node_dic[i].c_list:
        p_list[j] = i
        root -= j
p_list[root] = -1

for i in range(n):
    j = i
    while p_list[j] > -1:
        j = p_list[j]
        d_list[i] += 1

for i in range(n):
    if p_list[i] == -1:
        t_list[i] = t_list[i] + "root"
    else:
        if len(node_dic[i].c_list):
            t_list[i] = t_list[i] + "internal node"
        else:
            t_list[i] = t_list[i] + "leaf"

for i in range(n):
    s = "node %d: parent = %d, depth = %d, %s," %(i, p_list[i], d_list[i], t_list[i])
    print s, node_dic[i].c_list