#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;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxhbGdvcml0aG0+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE1BWE4gPSAxZTUgKyA1LCBNQVhMID0gMTc7CgppbnQgZHBbTUFYTl1bTUFYTF0sIFdbTUFYTl0sIExbTUFYTl0sIFQsIE4sIFEsIHQgPSAxOwoKaW50IHF1ZXJ5KGludCB1LCBpbnQgayl7CiAgaW50IGxvZyA9IDE7CiAgZm9yKDsgKDE8PGxvZyk8PUxbdV07IGxvZysrKTsKICBsb2ctLTsKICBmb3IoOyBsb2c+PTA7IC0tbG9nKSBpZihkcFt1XVtsb2ddICE9IC0xICYmIFdbZHBbdV1bbG9nXV0gPj0gaykgdSA9IGRwW3VdW2xvZ107CiAgcmV0dXJuIHU7Cn0KCmludCBtYWluKCl7CiAgc2NhbmYoIiVkIiwgJlQpOwogIHdoaWxlKFQtLSl7CiAgICBpbnQgdSwgazsKICAgIHNjYW5mKCIlZCAlZCIsICZOLCAmUSk7CiAgICBmb3IoaW50IGk9MDsgaTxOOyArK2kpCiAgICAgIGZvcihpbnQgaj0xOyAoMTw8aik8TjsgKytqKSBkcFtpXVtqXSA9IC0xOwogICAgZm9yKGludCBpPTE7IGk8TjsgKytpKXsKICAgICAgc2NhbmYoIiVkICVkIiwgJnUsICZXW2ldKTsKICAgICAgZHBbaV1bMF0gPSB1LCBMW2ldID0gTFt1XSArIDE7CiAgICB9CiAgICBXWzBdID0gMTsKICAgIGZvcihpbnQgaj0xOyAoMTw8aik8TjsgKytqKQogICAgICBmb3IoaW50IGk9MDsgaTxOOyArK2kpCiAgICAgICAgaWYoZHBbaV1baiAtIDFdICE9IC0xKSBkcFtpXVtqXSA9IGRwW2RwW2ldW2ogLSAxXV1baiAtIDFdOwogICAgcHJpbnRmKCJDYXNlICVkOlxuIiwgdCsrKTsKICAgIHdoaWxlKFEtLSl7CiAgICAgIHNjYW5mKCIlZCAlZCIsICZ1LCAmayk7CiAgICAgIHByaW50ZigiJWRcbiIsIHF1ZXJ5KHUsIGspKTsKICAgIH0KICB9CiAgcmV0dXJuIDA7Cn0=