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
n = int(input())
data = [list(map(int, input().split())) for i in range(n)]
ID = 0
parent = -1
depth = 0
sect = data[0][2:]
print("note {}: parent = {}, depth = {}, root, {}".format(ID, parent, depth, sect))

parent = 0
depth = 1

def rootedTrees(ID, parent, depth):
    if data[ID][1] == 0:
        sect = []
        print("note {}: parent = {}, depth = {}, leaf, {}".format(ID, parent, depth, sect))
    else:
        sect = data[ID][2:]
        print("note {}: parent = {}, depth = {}, internal node, {}".format(ID, parent, depth, sect))
        parent = ID
        for i in sect:
            rootedTrees(i, parent, depth+1)

for i in sect:
    rootedTrees(i, parent, depth)



Fixed, accepted submission:
#coding:utf-8

n = int(input())
T = [list(map(int, input().split())) for i in range(n)]
A = []
def parentSearch():
    numList = []
    for t in T:
        if t[1] != 0:
            for num in t[2:]:
                numList.append(num)
    numList.sort()
    for i in range(n-1):
        if numList[i] != i:
            return i


def rootedTrees(node, parent, depth):
    t = T[node]
    if t[1] != 0:
        if parent == -1:
            kind = "root"
        else:
            kind = "internal node"
        A.append([t[0], parent, depth, kind, t[2:]])
        parent = node
        for i in t[2:]:
            rootedTrees(i, parent, depth+1)
    else:
        if parent == -1:
            kind = "root"
        else:
            kind = "leaf"
        A.append([t[0], parent, depth, kind, []])


def Merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append([510000])
    R.append([510000])
    i,j = 0,0
    for k in range(left,right):
        if L[i][0] <= R[j][0]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def MergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right)//2
        MergeSort(A, left, mid)
        MergeSort(A, mid, right)
        Merge(A, left, mid, right)

MergeSort(T, 0, n)
node = parentSearch()
if node == None:
    node = 0
depth = 0
parent = -1
rootedTrees(node, parent, depth)
MergeSort(A, 0, n)

for t in A:
    print("node {}: parent = {}, depth = {}, {}, {}".format(t[0],t[1],t[2],t[3],t[4]))