Unique Binary Tree Traversal

You are given a binary tree in level-order form. Each node is represented as a tuple $(v, l, r)$ where $v$ is the value of the node, and $l$ and $r$ represent the values of the left and right child respectively. A value of -1 indicates that the corresponding child is missing.

Your task is to perform a unique traversal defined as follows:

1. Traverse the left subtree in preorder (i.e., visit the node, then its left child, then its right child).
2. Visit the root node.
3. Traverse the right subtree in inorder (i.e., visit the left child, then the node, then the right child).

Formally, if $L$ is the left subtree and $R$ is the right subtree of the root, compute the result as: [ \text{Result} = \text{preorder}(L) \oplus [\text{root value}] \oplus \text{inorder}(R), ] where (\oplus) denotes concatenation.

For example, consider the binary tree represented by the tuples:

[(1, 2, 3), (2, -1, -1), (3, 4, 5), (4, -1, -1), (5, -1, -1)].

The left subtree of the root (node 1) is the tree rooted at 2. Its preorder traversal is [2]. The right subtree is the tree rooted at 3. Its inorder traversal is [4, 3, 5]. Including the root value gives the unique traversal: [2, 1, 4, 3, 5].

inputFormat

Input is read from standard input. The first line contains an integer $T$, the number of test cases. For each test case, the first line contains an integer $N$, the number of nodes in the binary tree. This is followed by $N$ lines, each containing three integers: $v$, $l$, and $r$, representing the value of the node and the values of its left and right children respectively. A value of -1 indicates that a child is missing.

outputFormat

For each test case, output a single line containing the unique traversal sequence. The sequence consists of integers separated by a single space.## sample

1
5
1 2 3
2 -1 -1
3 4 5
4 -1 -1
5 -1 -1

2 1 4 3 5