Problem:
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**

Incorrect submission (verdict: Wrong Answer):
# coding=utf-8
class Node():
    # About Type
    # parent = -1 ==> Root ==> 0
    
    # others ==> Internal ==> 2
    def __init__(self, id, parent, child):
        self.id = id
        self.parent = parent
        self.child = child

    def update(self):
        self.depth = 0
        back = -1
        if self.parent == -1:
            self.Type = "root"
            back = self.id
        elif self.child == []:
            self.Type = "leaf"
        else :
            self.Type = "internal node"
        return back

    def printInfo(self):
        print("node :" + str( self.id ), end = " :" )
        print("parent = " + str( self.parent ), end = ", " )
        print("depth = " + str( self.depth ), end = ", " )
        print( self.Type, end = ", " )
        print("[", end="")
        length = len( self.child )
        for i in self.child[0: length - 1]:
            print(str(i), end=", ")
        if length > 0:
            print( str(self.child[length-1]) , end="")
        print("]")


    def calcDepth(self, Tree):
        if self.parent == -1:
            self.depth = 0
        else :
            self.depth = Tree[self.parent].depth + 1
        for i in self.child:
            Tree[i].calcDepth(Tree)


def main():
    
    n = int( input() )
    InputData = []
    Tree = {} 

    tmp = []
    for i in range(n):
        tmp = [int(x) for x in input().split()] 
        InputData.append(tmp)
        
        Tree[tmp[0]] = Node(tmp[0], -1, tmp[2: 2+tmp[1]])

    for val in Tree.values():
        for i in val.child:
            Tree[i].parent = val.id

    for key in Tree.keys():
        tmp = Tree[key].update()
        if tmp != -1:
            root = tmp

    Tree[root].calcDepth(Tree)

    keys = list(Tree.keys())
    keys.sort()

    for key in keys:
        Tree[key].printInfo()

if __name__ == '__main__':
    main()



Fixed, accepted submission:
# coding=utf-8
class Node():
    # About Type
    # parent = -1 ==> Root ==> 0
    
    # others ==> Internal ==> 2
    def __init__(self, id, parent, child):
        self.id = id
        self.parent = parent
        self.child = child

    def update(self):
        self.depth = 0
        back = -1
        if self.parent == -1:
            self.Type = "root"
            back = self.id
        elif self.child == []:
            self.Type = "leaf"
        else :
            self.Type = "internal node"
        return back

    def printInfo(self):
        print("node " + str( self.id ), end = ": " )
        print("parent = " + str( self.parent ), end = ", " )
        print("depth = " + str( self.depth ), end = ", " )
        print( self.Type, end = ", " )
        print("[", end="")
        length = len( self.child )
        for i in self.child[0: length - 1]:
            print(str(i), end=", ")
        if length > 0:
            print( str(self.child[length-1]) , end="")
        print("]")


    def calcDepth(self, Tree):
        if self.parent == -1:
            self.depth = 0
        else :
            self.depth = Tree[self.parent].depth + 1
        for i in self.child:
            Tree[i].calcDepth(Tree)


def main():
    
    n = int( input() )
    InputData = []
    Tree = {} 

    tmp = []
    for i in range(n):
        tmp = [int(x) for x in input().split()] 
        InputData.append(tmp)
        
        Tree[tmp[0]] = Node(tmp[0], -1, tmp[2: 2+tmp[1]])

    for val in Tree.values():
        for i in val.child:
            Tree[i].parent = val.id

    for key in Tree.keys():
        tmp = Tree[key].update()
        if tmp != -1:
            root = tmp

    Tree[root].calcDepth(Tree)

    keys = list(Tree.keys())
    keys.sort()

    for key in keys:
        Tree[key].printInfo()

if __name__ == '__main__':
    main()