#include <bits/stdc++.h>
using namespace std;

typedef struct node{
	int parent;
	node(){
		parent=-1;
	}
}node;

int main(){
	int t,n,m,l,r;
	scanf("%d",&t);
	
	while(t--){
		node nod[10000];
		scanf("%d %d",&n,&m);
		for(int i=1;i<=n;i++){//建树
			scanf("%d %d",&l,&r);
			if(l!=-1) nod[l].parent=i;
			if(r!=-1) nod[r].parent=i;
		}

		while(m--){
			scanf("%d %d",&l,&r);
			vector<int> lv,rv;//分别存到根节点的路径

			while(l!=-1){
				lv.push_back(l);
				l=nod[l].parent;
			}
			while(r!=-1){
				rv.push_back(r);
				r=nod[r].parent;
			}
			
			int i=lv.size()-1,j=rv.size()-1;
			
			for(;i>=0,j>=0;i--,j--){
				if(lv[i]!=rv[j]){//找最小公共双亲
					break;
				}
			}
			cout<<i+j+2<<endl;//找出来的数字规律

//			cout<<"这是lv：";
//			for(int a=0;a<lv.size();a++) cout<<lv[a]<<" ";
//			cout<<endl<<"这是rv：";
//			for(int a=0;a<rv.size();a++) cout<<rv[a]<...