Ordering Trees
By Carlos Guillen, ICMC - USP 
Brazil
By Carlos Guillen, ICMC - USP Brazil
It is well know that the he Earl of Lemongrab is the weirdest guy in the Candy Kingdom, but his latest obsession has gone too far: he is trying to find out the order of all the things!
So far he has been succeeding on a lot of ordering problems, but he is getting mad because he found a problem he cannot solve: Given a rooted tree consisting of N vertices, where each vertex i has a value Vi, he tried to find out the increasing order of all the values in the subtree rooted at vertex X.
He did well for a couple of subtrees, but then he got tired and noticed that no one would be able to accomplish this task in short time. In order to relieve his frustration he asked you to answer M queries: for a given vertex X tell him what is the K-th smallest value in its subtree.
The first line contains an integer T (1 ≤ T ≤ 35), the number of test cases.
The first line of each test case contains two integers N and M (1 ≤ N, M ≤ 105), the number of vertices and the number of queries, respectively.
We will assume that the tree vertices are identified by integers from 1 to N and that the root of the tree is the vertex 1. The next line contains a sequence of integers V1, V2, ..., Vn (1 ≤ Vi ≤ 109), the values of each vertex.
Each of the next N - 1 lines contains two integers Ai and Bi (1 ≤ Ai, Bi ≤ N), the pairs of vertices connected by an edge on the tree. The tree is conected and valid.
The next M lines contain the queries, each line containing two integers X and K (1 ≤ X, Ki ≤ N), it is, find the he K-th smallest value in the subtree rooted at X. It is guaranteed that each query is valid.
For each test case print a single line containing the answers to the queries in the order they appear in the input, each answer should be followed by a single space (even for the last query).
| Sample Input | Sample Output |
|
4 1 1 10 1 1 3 3 1 1 1 1 2 3 2 1 3 2 2 3 1 3 2 5 6 7 1 2 3 1 1 2 3 1 6 2 1 5 1 2 3 7 2 1 6 3 2 4 3 1 5 3 1 4 3 3 |
10 |