Given the relationship of the nodes in a tree, construct the tree and output it in the pre-order. Each node has unique integer identification (ID), but all IDs may not be consecutive.
There are multiple test cases. Each test case begins with an integer N, denoting the number of relations in the tree. In the following N lines, each line contains two integers a and b, which means node a is node b’s parent. After that, the next line contains an integer R, which represents the root of the tree. You can assume that all the nodes will be on the same tree. The input is terminated by N = 0.
Case 1: 1 <= N <=10 , 1 <= a,b <= 20
Case 2: 1 <= N <=100 , 1 <= a,b <= 200
Case 3: 1 <= N <=1000 , 1 <= a,b <= 2000
Case 4: 1 <= N <=1000 , 1 <= a,b <= 2000000
For each test case, print the pre-order of the tree. In each level, traverse the node with smaller ID first.