human
What is 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....
impor
assistant
#Here is Python code to print the information of each node in the following format ordered by IDs:
.
t sys
sys.setrecursionlimit(2147483647)

class Node:
  def __init__(self,p,l,r):
    self.p=p
    self.l=l
    self.r=r

def getDepth(u):
  #d=0
  #while T[u].parent!=None:
  #  u=T[u].parent
  #  d+=1
  #return d
  return D[u]

def setDepth(u,p):
  global D
  D[u]=p
  if T[u].r!=-1:
    #print("debug:",T[u].r)
    setDepth(T[u].r,p)
  if T[u].l!=-1:
    setDepth(T[u].l,p+1)

def getChildren(u):
#def printChildren(u):
  C=[]
  c=T[u].l
  while c!=-1:
    #print(c,end=', ')
    C.append(str(c))
    c=T[c].r
  return C

n=int(input())
#T=[Node(-1,-1,-1)]*n
T=[Node(-1,-1,-1) for _ in range(n)]
for _ in range(n):
  C=list(map(int,input().split()))
  if C[1]>0:
    T[C[0]].l=C[2]
  k=C[1]
  for i in range(2,k+2):
    T[C[i]].p=C[0]
    if i+1<k+2:
      T[C[i]].r=C[i+1]

#for i in range(n):
#  print(i,":",T[i].r)
#exit(0)

r=-1
for i in range(n):
  if T[i].p==-1:
    r=i
    break
D=[-1]*n
setDepth(r,0)

for i in range(n):
  node=T[i]
  C=getChildren(i)
  d=getDepth(i)
  t='root' if T[i].p==-1 else 'leaf' if T[i].l==-1 else 'internal node'
  print('node '+str(i)+': parent = '+str(T[i].p)+', depth = '+str(d)+', '+t+', [',end='')
  print(', '.join(C),end='')
  print(']')