Given a tree G(V, E) with at most N nodes, print its preorder traversal sequence. Each node is labeled by a unique integer number from 1 to N, and in case that the node has more than one child, the one who is labeled by smaller number should be visited first. Root node is always node 1.
Input begins with an integer T, the number of test cases. Each test case would be in the following format.
Line 1: An integers: N, means the size of the tree.
The following are N-1 lines.
Line i (2<=i<=N): Two integers: x y, separated by a blank, indicating that x and y are connected.
Limit : N<=1000
For each test case outputs one lines, the preorder traversal sequence.
Each node number should be separated by one space.