Description

You are a legendary explorer (who is very proficient at using bullwhips) preparing to enter forgotten ancient underground mazes to seek hidden treasures. The rooms and passages for each maze form a standard Binary Tree structure. Per maze, each room is assigned a unique integer identifier.

To safely navigate each maze and avoid deadly traps, you must strictly follow the "Exploration Spells" recorded on an ancient scroll. The scroll documents three safe exploration spells and the spell to follow for each maze:

• PRE: Preorder traversal
• IN: Inorder traversal
• POST: Postorder traversal

Your task is to write a C/C++ program that reads, for each maze, the connection map of the maze rooms along with the exploration spell from the scroll, and outputs the correct sequence of rooms to visit for the maze.

However, due to the passage of time, some texts on the scroll have become blurred or corrupted. If the spell read by your program is not one of the three standard commands (e.g., PREE, ORDER, or other unknown strings), your program must immediately warn you by outputting Invalid command to prevent further exploration for that maze and save your life.

Maze Map Representation: For each maze, you will first be given the total number of rooms N. The following N lines each contain three integers V, L, and R:

• V is the identifier of the current room.
• L is the identifier of the room connected via the left passage.
• R is the identifier of the room connected via the right passage.
• If there is no passage in a particular direction (a dead end), the corresponding value will be -1.
• Note: The first room V given in the input for each maze is ALWAYS the entrance (Root) of that maze.

Your program MAY use C++ standard library headers.

Input

The first line contains a positive integer M, representing the total number of mazes to explore.

For each maze: The first line contains the integer N and the exploration spell, separated by a space. The following N lines each contain three integers V, L, and R, representing the rooms and their connections.

• 0 < M <= 20
• 0 < N <= 10^5
• You can assume that the sum of N for all mazes in a single test case sum(N) <= 5 * 10^5.
• Room identifiers V are guaranteed to fit within a standard 32-bit signed integer.

Output

For each maze, output the sequence of room identifiers to explore on a single line, separated by a single space. Each line of output must be terminated by a newline character ('\n'). If the exploration spell is invalid, output: Invalid command.

Sample Input  Download

Sample Output  Download

Tags

Discuss