A signal relay network is organized as a rooted tree of towers. Every tower has a unique identifier. Exactly one tower is the network's master tower and has no upstream tower; every other tower reports to exactly one upstream tower, which is itself one of the towers in the network. Classify every tower into exactly one of three roles:
ROOT -- the tower has no upstream tower. (This applies to exactly the master tower, regardless of how many towers report to it.)LEAF -- the tower has an upstream tower, and no other tower reports to it.RELAY -- the tower has an upstream tower, and at least one other tower reports to it.Report the role of every tower, ordered by identifier.
n, the number of towers.n lines contains two integers id and p: the tower's identifier, and the identifier of the tower it reports to, or p = 0 if this tower is the master tower with no upstream. Rows may appear in any order.Print n lines, sorted by ascending id, each formatted as id ROLE where ROLE is one of ROOT, LEAF, RELAY.
p is either 0 or equal to the id of another tower listed in the input.Example 1
Input
5 1 0 2 1 3 1 4 2 5 2
Expected
1 ROOT 2 RELAY 3 LEAF 4 LEAF 5 LEAF
Explanation
Tower 1 has p=0, so it is ROOT. Towers 2 and 3 both report to tower 1. Tower 2 has towers 4 and 5 reporting to it, so tower 2 is RELAY. Tower 3 has nothing reporting to it, so it is LEAF. Towers 4 and 5 both report to tower 2 and have nothing reporting to them, so both are LEAF.
Example 2
Input
1 1 0
Expected
1 ROOT
Explanation
There is only one tower in the whole network, and it has p=0. Its role is ROOT -- a tower's role depends only on whether it has an upstream tower, never on whether anything reports to it, so a lone master tower is still ROOT even though nothing reports to it (it is not LEAF).
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →