Server Time: Sun Oct 20, 2019 1:43 am
Welcome ( logout
1128 - Greatest Parent
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 64 MB

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 if 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 Input

Output for Sample Input

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

Note

Dataset is huge. Use faster I/O methods.


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan