The yearly Multi-University Training Contest is coming, and ?? had already prepared an interesting and challenging problem for all those intelligent brains. However, when he told teammates about his “wonderful idea”, it really shocked him that all of them, except himself, had already seen an existing problem with the same trick.So he need to rack his brain again.
But nothing is difficult for a willing heart. After thinking about it all through the night, he came up with a new problem:
The original rooted tree has n nodes, numbered from 1 to n. Each node has a value, all of these values form a permutation of [1,n]. We reset these values by the following way:
new value(P) = max{previous value(Q)|Q is in the subtree with root P}
Given the new tree(each node’s number, it’s neighbors and it’s value), your job is to restore its original appearance.
Note that the root of the given tree is unspecified.
First line gives the number of test cases T.
Each cases begins with n(the number of nodes).Next line gives n integers, the i’th integers means i-th node’s value. Then n-1 lines, each line has two integers a and b, describes the edge connecting node a and node b..
T<=20, 1<=n<=100000. All node’s values are in range [1,n]. The given edges construct a tree of nodes 1 to n.Sum of n in all cases<=200000.
There may be blank lines before each case.
For each test case, first output "Case #x: ".If it’s impossible to restore the original tree, output “Impossible”. Otherwise, output original values of nodes 1,2,...n in order, separated by spaces.If there exist multiple answers, the lexicographically smallest one is needed.