10601060 SUSTech Online Judge
Problem 1060 --Traversal tree three in one

1060: Traversal tree three in one

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 450  Solved: 245
[Submit][Status][Web Board]

Description

Give you a binary tree T. Please print the:

pre/ in/ post order Traversal of the tree.

Input

First line is an integer T, which is the number of test cases. (1 <= T <= 50)

For each test case, there will be an integer in a single line N (1 <= N <= 1024). N is the number of nodes. The nodes are numbered from 1 to N.

Then there will be N – 1 lines with two integer x, y for each line. (1 <= x, y <= N)

x y means x is the farther of y. What’s more, we guarantee the input file is a tree. And the child appears first is the left child, the other one appears later is right child.

Output

For each test case, you should print three lines:

The 1st/2nd/3rd line is the pre/in/post order traversal of the Tree.

Sample Input

1
8
1 4
1 3
4 2
2 7
3 5
3 6
6 8

Sample Output

1 4 2 7 3 5 6 8
7 2 4 1 5 3 8 6
7 2 4 5 8 6 3 1

HINT

Easy problem.

Source

[Submit][Status]