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

const long long MAXN = 2e5+7, MAXK = 30;
long long n, m, d[MAXN], s[MAXN], t[MAXN], dep[MAXN], in[MAXN], out[MAXN], tt, st[MAXK][MAXN], wh[MAXN], step[MAXN], pwr[MAXN];
bool iii[MAXN];
vector<long long> adj[MAXN], nz, nz1;

void dfs1(long long u, long long p)
{
    tt++;
    dep[u] = dep[p]+1;
    in[u] = tt;
    for(long long v: adj[u])
    {
        if(v == p) continue;
        dfs1(v, u);
    }
    out[u] = tt;
    tt++;
    return;
}

void dfs2(long long u, long long p)
{
    nz.push_back(u);
    for(long long v: adj[u])
    {
        if(v == p) continue;
        dfs2(v, u);
        nz.push_back(u);
    }
    return;
}

long long query(long long l, long long r)
{
    long long len = r-l+1;
    return min(st[step[len]][l], st[step[len]][r-step[len]+1]);
}

vector<int> solve(vector<pair<int, int> > R, vector<long long> D, vector<int> S, vector<int> T, vector<bool> I)
{
    vector<long long> ans;
    m = D.size();
    for(auto x: R)
    {
        adj[x.first+1].push_back(x.second+1);
        adj[x.second+1].push_back(x.first+1);
        n = max(n, x.first);
        n = max(n, x.second);
    }
    for(long long i = 0; i < m; i++) d[i+1] = D[i];
    for(long long i = 0; i < m; i++) s[i+1] = S[i]+1;
    for(long long i = 0; i < m; i++) t[i+1] = T[i]+1;
    for(long long i = 0; i < m; i++) iii[i+1] = I[i];
    dfs1(1, 0);
    dfs2(1, 0);
    //for(auto x: nz) cout<<x<<" ";
    //cout<<"\n";
    pwr[0] = 1;
    for(long long i = 1; i < MAXK; i++)
    {
        pwr[i] = pwr[i-1]*2;
    }
    step[1] = 0;
    for(long long i = 2; i <= nz.size(); i++)
    {
        if(pwr[step[i-1]]*2 <= i) step[i] = step[i-1]+1;
        else step[i] = step[i-1];
    }
    for(long long i = 0; i < nz.size(); i++)
    {
        nz1.push_back(dep[nz[i]]);
        wh[nz[i]] = i;
        st[0][i] = dep[nz[i]];
    }
    for(long long j = 1; j < MAXK; j++)
    {
        for(long long i = 0; i+pwr[j]-1 < nz.size(); i++)
        {
            st[j][i] = min(st[j-1][i], st[j-1][i+pwr[j-1]]);
        }
    }
    for(long long i = 1; i <= m; i++)
    {
        if(!iii[i]) ans.push_back(0);
        long long mini;
        if(dep[s[i]] > dep[t[i]]) swap(s[i], t[i]);
        if(in[s[i]] <= in[t[i]] && out[s[i]] >= out[t[i]]) mini = dep[s[i]];
        else mini = query(wh[s[i]], wh[t[i]]);
        //cout<<s[i]<<" "<<t[i]<<" "<<mini<<"\n";
        ans.push_back(dep[s[i]]+dep[t[i]]-mini);
    }
    return ans;
}
/*
9 5
0 1
1 2
2 3
3 4
4 5
3 6
6 7
6 8
0 5 2 0
100 4 8 1
1000 5 7 1
100000 1 2 1
10000 8 7 0
*/
