https://www.bilibili.com/read/cv13619734/

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int N=1e5+10;
const int M=32;
int n,m;
int h[N],e[N*2],ne[N*2],idx;

void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

int depth[N];
int f[N][M];

void bfs(int root)
{
    queue<int> q;
    q.push(root);
    depth[root]=1;

    while(q.size())
    {
        int t=q.front();
        q.pop();

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(!depth[j])
            {
                depth[j]=depth[t]+1;
                q.push(j);
                f[j][0]=t;
                for(int k=1;k<M;k++)
                {
                    f[j][k]=f[f[j][k-1]][k-1];
                }
            }
        }
    }
}

int lca(int a,int b)
{
    if(depth[a]<depth[b])swap(a,b);

    for(int k=M-1;k>=0;k--)
    {
        if(depth[f[a][k]]>=depth[b])a=f[a][k];
    }

    if(a==b)return a;

    for(int k=M-1;k>=0;k--)
    {
        if(f[a][k]!=f[b][k])
        {
            a=f[a][k],b=f[b][k];
        }
    }
    return f[a][0];
}

signed main()
{
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    int root=0;
    for(int i=0;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(b==-1)
        root=a;
        else 
        {
            add(a,b);
            add(b,a);
        }
    }
    bfs(root);
    scanf("%d",&m);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        //cout<<lca(a,b)<<endl;
        int p=lca(a,b);
        if(p==a)cout<<1<<endl;
        else if(p==b)cout<<2<<endl;
        else cout<<0<<endl;
    }
    return 0;
}