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 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 elems.items():
        print('node {0}: parent = {1[0]}, depth = {1[1]}, {1[2]}, '.format(key, value), end='')
        print (value[-1])


Fixed, accepted submission:
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])