A tree is a connected graph with no cycles. In this problem, you are given a rooted tree, where each node contains an integer value. And the value of a node is strictly greater than the value of its parent. Now you are given a node and an integer query. You have to find the greatest possible parent of this node (may include the node itself), whose value is greater than or equal to the given query integer.
Input
Input starts with an integer T (≤ 5), denoting the number of test cases.
The first line of a case is a blank line. The next line contains two integers N (1 ≤ N ≤ 105), q (1 ≤ q ≤ 50000) where N denotes the number of nodes and q denotes the number of queries. The nodes are numbered from 0 to N-1.
Then there will be N-1 lines. The ith (1 ≤ i < N) line contains two integers pi and si (0 ≤ pi < i, 1 ≤ si < 231). pi denotes the parent and si denotes the value of the ith node, respectively. Assume that the given tree is correct and follows the restrictions as stated. You can assume that the 0th node is the root and its value is 1.
Each of the next q lines contains a query. Each query contains two integers: k and v (1 ≤ k < N, 1 ≤ v ≤ sk).
Output
For each case, print the case number in a line. Then for each query, print the index of the greatest parent of node k with value greater than or equal to v. You can assume that a solution exists.
Sample
Sample Input | Sample Output |
---|---|
1 7 4 0 3 0 4 0 2 1 4 2 7 2 10 5 1 4 2 5 4 6 10 | Case 1: 0 1 2 6 |
Notes
Dataset is huge. Use faster I/O methods.