Level Order Traversal

Problem statement

A communications tree distributes a message outward from a central station. A report groups stations by how many links away they are from the root, listing stations from left to right within each group. Your task Produce the level-order traversal of the binary tree. Print one level per line, starting with the root level. Important details Use a queue so that all nodes at one depth are visited before the next depth. Missing child positions are not printed. Keep left children before right children when they belong to the same parent. An empty tree has no levels. Worked example Root 4 with children 2 and 8 produces line 4 followed by line 2 8. Both children are one link from the entrance.

Input format

The first line contains n. The next n lines contain value left right for nodes 0 through n-1. Child indices are -1 when absent. Node 0 is the root when n > 0. The records form one valid binary tree; n = 0 represents an empty tree.

Output format

Print one space-separated line per level. Print EMPTY for an empty tree.

Constraints

0 <= n <= 2000; -1000 <= value <= 1000. Child indices are -1 or valid node indices; no cycles or shared children.

Sample input

3
4 1 2
2 -1 -1
8 -1 -1

Sample output

4
2 8