#include <stdio.h>
#include <algorithm>

using namespace std;

const int MAXN = 1e5 + 5, MAXL = 17;

int dp[MAXN][MAXL], W[MAXN], L[MAXN], T, N, Q, t = 1;

int query(int u, int k){
  int log = 1;
  for(; (1<<log)<=L[u]; log++);
  log--;
  for(; log>=0; --log) if(dp[u][log] != -1 && W[dp[u][log]] >= k) u = dp[u][log];
  return u;
}

int main(){
  scanf("%d", &T);
  while(T--){
    int u, k;
    scanf("%d %d", &N, &Q);
    for(int i=0; i<N; ++i)
      for(int j=1; (1<<j)<N; ++j) dp[i][j] = -1;
    for(int i=1; i<N; ++i){
      scanf("%d %d", &u, &W[i]);
      dp[i][0] = u, L[i] = L[u] + 1;
    }
    W[0] = 1;
    for(int j=1; (1<<j)<N; ++j)
      for(int i=0; i<N; ++i)
        if(dp[i][j - 1] != -1) dp[i][j] = dp[dp[i][j - 1]][j - 1];
    printf("Case %d:\n", t++);
    while(Q--){
      scanf("%d %d", &u, &k);
      printf("%d\n", query(u, k));
    }
  }
  return 0;
}