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


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

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    node_list = [None] * int(lines[0])  
    child_parent_map = [None] * int(lines[0])

    # Create the list of Node
    for line in lines[1:]:
        node_id, _, *children = [int(x) for x in line.strip().split(" ")]
        node_list[node_id] = Node(children=children)
        for child in children:
            child_parent_map[child] = node_id

    # Set the parent_id of each node
    for node_id, node in enumerate(node_list):
        if child_parent_map[node_id] is not None:
            node.parent_id = child_parent_map[node_id]

    # Set the depth of each node
    for node_id, node in enumerate(node_list):
        current_id = node_id
        current_depth = 0
        while True:
            if current_id == 0:
                node.depth = current_depth
                break
            else:
                current_id = node_list[current_id].parent_id
                current_depth += 1

    # Output
    for node_id, node in enumerate(node_list):
        print("node %d: parent = %d, depth = %d, leaf, %s" % (node_id, node.parent_id, node.depth, node.children))

Fixed, accepted submission:
#!/usr/bin/env python3

import sys


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

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    node_list = [None] * int(lines[0])  
    child_parent_map = [None] * int(lines[0])

    # Create the list of Node
    for line in lines[1:]:
        node_id, _, *children = [int(x) for x in line.strip().split(" ")]
        node_list[node_id] = Node(children=children)
        for child in children:
            child_parent_map[child] = node_id

    # Set the parent_id of each node
    for node_id, node in enumerate(node_list):
        if child_parent_map[node_id] is not None:
            node.parent_id = child_parent_map[node_id]

    # Set the depth of each node
    for node_id, node in enumerate(node_list):
        current_id = node_id
        current_depth = 0
        while True:
            # if current_id == 0:
            if node_list[current_id].parent_id == -1:
                node.depth = current_depth
                break
            else:
                current_id = node_list[current_id].parent_id
                current_depth += 1

    # Output
    for node_id, node in enumerate(node_list):
        if node.parent_id == -1:
            node_type = "root"
        elif len(node.children) == 0:
            node_type = "leaf"
        else:
            node_type = "internal node"

        print("node %d: parent = %d, depth = %d, %s, %s" % (node_id, node.parent_id, node.depth, node_type, node.children))