#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int N = 100010;

int bt[N];

int main() {
    int t;  // 表示有多少测试数据
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; ++i) {
            int l, r;
            scanf("%d %d", &l, &r);
            if (l >= 0) bt[l] = i;
            if (r >= 0) bt[r] = i;
        }
        while (m--) { // m次询问  寻找第一个公共父亲节点
            int x, y, count = 0;
            scanf("%d %d", &x, &y);
            vector<int> xparent;
            vector<int> yparent;

            xparent.push_back(x);
            while (bt[x] != 0) {
                x = bt[x];
                xparent.push_back(x);   // 节点x的父辈节点
            }

            yparent.push_back(y);
            while (bt[y] != 0) {
                y = bt[y];
                yparent.push_back(y);   // 节点x的父辈节点
            }

            int i = xparent.size() - 1, j = yparent.size() - 1;
            while (i >= 0 && j >= 0 && xparent[i] == yparent[j]) {
                --i;
                --j;
            }
            count = i + j + 2;
            printf("%d\n", count);
        }
    }

    return 0;
}