11531153 SUSTech Online Judge
Problem 1153 --Preinpost [Easy]

1153: Preinpost [Easy]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 303  Solved: 262
[Submit][Status][Web Board]

Description

Write a program to print the pre order, in order and post order traversal of the given binary tree.

Input

The first line will be an integer T (1≤T≤10), which is the number of test cases.  

For each test data:

The first line contains one integer N (1≤N≤10^4) — the number of the nodes.

Each of the next N - 1 lines contain two integers a and b, which means node a is the father of node b (1≤a, b≤N). If a node has two sons, the son appeared earlier is the left son and another is the right son. If a node only has one son, the son is the left son.

Output

For each test cases, print three lines: the pre order, in order and post order traversal of the given binary 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

Source

[Submit][Status]