Directory Tree Role Ledger

A build system keeps a flat table of directories. Every directory has a unique id from 0 to n - 1. Every directory except one records the id of its parent directory; exactly one directory has no parent at all and sits at the top of the tree. Classify every directory into exactly one of three roles:

• Root -- the one directory with no parent.
• Leaf -- a directory that owns no subdirectories (and is not the root).
• Branch -- any other directory: it has a parent and owns at least one subdirectory.

Given the parent pointers, report the role of every directory.

Input format

The first line contains an integer n. The second line contains n integers parent_0 parent_1 ... parent_{n-1}, where parent_i is the id of directory i's parent, or -1 if directory i is the root.

Output format

Print n lines, one per directory, ordered by increasing id: <id> <role> where <role> is one of Root, Leaf, Branch.

Constraints

• 1 <= n <= 10^5
• Exactly one index has parent_i = -1.
• Every other parent_i is a valid directory id (0 <= parent_i < n, parent_i != i), and the parent pointers form a single tree rooted at the -1 directory (no cycles, every directory reachable from the root).

5
-1 0 0 1 1

0 Root
1 Branch
2 Leaf
3 Leaf
4 Leaf

1
-1

0 Root