2017-04-09 14:32 阅读 809

Old Labels

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 non-negative 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 pi 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 pi for cities without any road starting from it, namely {pathi}, 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?


There 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 c-th smallest path in {pathi}.


For each query, if there are less than c cities without any road starting from it, print "Out of range." (without quotes), otherwise, print the c-th smallest path in one line with labels in the path separated by one space. Print a blank line after each case.

Sample Input

8 5
0 1
0 2
0 3
1 4
2 5
3 6
3 7
Sample Output

0 0
0 1
1 0
2 0
Out of range.

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

1条回答 默认 最新