
ZOJ Problem Set  3489
Several thousand years ago, there was an ancient kingdom consisting of n cities numbered from 0 to n  1. The city numbered 0 was the capital of the kingdom and there were n  1 directed roads connecting the capital and other cities so that every other city could be reached from the capital. In the National Library, there was a dusty book in a deep recess which recorded an amazing story. The story said that long long ago, for every road there had been a specified nonnegative integer labeled onto it. What's more, for every city, we could find that all the roads starting from it had different labels. So with these labels, every city i could be expressed by the path with a series of numbers p_{i} from the capital to it in order. But the book didn't say anything about how the roads were labeled and it seemed the way the roads were labeled was no longer known by anybody. One day the king in the kingdom, Takamina, decided to relabel the roads so that the conditions in the story were satisfied. Also, a specified condition should also be met that the list of p_{i} for cities without any road starting from it, namely {path_{i}}, was lexicographically minimized. To compare two lists, we first sort both lists separately and compare them as strings of paths (do as how strings compare while the elements of the strings are paths). To compare two paths, we also compare them as strings of numbers. So you, the most talented programmer, can you solve the problem? InputThere are multiple test cases. The first line of the input is an integer T ≈ 100 indicating the number of test cases. For each test case, the first line are two integers n and Q (1 ≤ n ≤ 1000, 0 ≤ Q ≤ n). Next n  1 lines each containing two integers u and v indicating a road from u to v. Next Q lines each containing one integer c (1 ≤ c ≤ n) indicating a query to the cth smallest path in {path_{i}}. OutputFor each query, if there are less than c cities without any road starting from it, print "Out of range." (without quotes), otherwise, print the cth smallest path in one line with labels in the path separated by one space. Print a blank line after each case. Sample Input1 8 5 0 1 0 2 0 3 1 4 2 5 3 6 3 7 1 2 3 4 5 Sample Output0 0 0 1 1 0 2 0 Out of range. HintLabeling the roads to {1, 2, 0, 0, 0, 0, 1} in the order as the sample would lead to the minimized list of paths, which is {{0, 0}, {0, 1}, {1, 0}, {2, 0}}. Author: ZHUANG, Junyuan Contest: The 8th Zhejiang Provincial Collegiate Programming Contest 