human
Give me a Python code to print the information of each node in the following format ordered by IDs: given the following:
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

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

Constraints

* 1 ≤ n ≤ 100000

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 c1 c2 ... ck

where id is the node ID of u, k is the degree of u, c1 ... ck are node IDs of 1st, ... kth 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, [c1...ck]

p is ID of its parent....
The above is tricky. Write me a correct solution in PYTHON3.
assistant
#Here is Python code to print the information of each node in the following format ordered by IDs:
.

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)