You are given a tree with N nodes and each node has some value assigned to it. Now you are given Q tasks of the form X K.
For each task, you have to find the path starting from X such that sum of nodes in the path is at least K and it contains minimum number of nodes. If such path exists, print the count of nodes in the path, else print -1.
Input format
- First line: Two space-separated integers N and Q
- Second line: N space-separated integers (denoting vali)
- Next N -1 lines: Two space-separated integers U and V (denoting an edge between the nodes U and V)
- Next Q lines:Two space-separated integers X and K
Output format
For each task, print the required answer in a new line.
Input Constraints
\(1 \le N \le 10^5\)
\(1 \le Q \le 10\)
\( 1\le val_i \le 10^9\)
\(1 \le U,V \le N\)
\(1 \le X \le N\)
\(1 \le K \le 10^{10}\)
For task 1: There are two paths from 1 .
1->2->4, sum=9
1->4 , sum=7
So path with minimum number of nodes and sum>=6 is 1->4 as it has only two nodes while the other path has three nodes.
For task 2: Paths with minimum number of nodes and sum>=5 are 2->1 and 2->3. The path 2->1->4 has sum=10 but it has three nodes.
