The Kth Path

All submissions for this problem are available.
WARNING: The Input files may be as large as 8 MB. Use faster I/O methods.
There is a tree, consisting of N nodes. A path is a sequence of one or more nodes of this tree, where every two adjacent nodes are connected by an edge and no node is visited twice. Generally, there are N^{2} paths. Note that we are counting paths from each node onto itself as well. One path is smaller than another if the sequence of nodes of the first path is lexicographically smaller than the sequence of nodes of the second path (by usual rules).
Thus (1,3,2) will be smaller than (1,3,4,5). And (2,4) will be smaller than (3).
Every day, Lucy writes out a path on a sheet of paper. On the first day, she writes the lexicographically smallest path. On the second day, she writes the lexicographically second smallest path, and so on. Generally, on the K^{th} day, Lucy writes out the lexicographically K^{th} smallest path.
Nana likes to read Lucy's notes about the paths in the tree. She is curious about the path that will be written on the Q^{th} day. Could you please help her?
Input
The first line of input consists of a single integer T, the number of the test cases. Then, there are T test cases, given in the following form: the first line of the test case consists of an integer N, the number of nodes and an integer Q, the number from the statement. Then, N1 lines follow. Each such line will consist of two integers X and Y with the meaning that there's an edge, connecting nodes X and Y in the tree. You may assume that you are always given a valid tree.
Output
For every test case, output the lexicographically Q^{th} smallest path in the given tree on a single line, without leading or trailing spaces. There should be exactly one space between successive nodes in the path. Output the answer to the t^{th} test case should be given on the t^{th} line.
Constraints
1 ≤ N ≤ 100000 1 ≤ Q ≤ N^{2} 1 ≤ Sum of N over all the test cases in the single file ≤ 1000000
Sample Input
3 6 21 1 2 2 3 2 4 2 5 2 6 7 35 1 2 1 3 3 4 4 5 4 6 4 7 6 16 1 2 1 3 1 4 2 5 1 6
Sample Output
4 2 1 5 4 7 3 1 2 5
Explanation
In the first test case, there are 36 paths in total. The lexicographically smallest first 21 paths are
01: 1 02: 1 2 03: 1 2 3 04: 1 2 4 05: 1 2 5 06: 1 2 6 07: 2 08: 2 1 09: 2 3 10: 2 4 11: 2 5 12: 2 6 13: 3 14: 3 2 15: 3 2 1 16: 3 2 4 17: 3 2 5 18: 3 2 6 19: 4 20: 4 2 21: 4 2 1
Author:  xcwgf666 
Tester:  gamabunta 
Editorial  http://discuss.codechef.com/problems/KTHPATH 
Tags  acmkgp13, dfs, graph, medium, tree, xcwgf666 
Date Added:  4102013 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, GO 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions