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

const int MAXN = 2e5+7, MAXK = 30;
int 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<int> adj[MAXN], nz, nz1;

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

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

int query(int l, int r)
{
    int 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<int> 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(int i = 0; i < m; i++) d[i+1] = D[i];
    for(int i = 0; i < m; i++) s[i+1] = S[i]+1;
    for(int i = 0; i < m; i++) t[i+1] = T[i]+1;
    for(int i = 0; i < m; i++) iii[i+1] = I[i];
    dfs1(1, 0);
    dfs2(1, 0);
    pwr[0] = 1;
    for(int i = 1; i < MAXK; i++)
    {
        pwr[i] = pwr[i-1]*2;
    }
    step[1] = 0;
    for(int 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(int i = 0; i < nz.size(); i++)
    {
        nz1.push_back(dep[nz[i]]);
        wh[nz[i]] = i;
        st[0][i] = dep[nz[i]];
    }
    for(int j = 1; j < MAXK; j++)
    {
        for(int 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(int i = 1; i <= m; i++)
    {
        if(!iii[i]) ans.push_back(0);
        int mini = query(wh[s[i]], wh[t[i]]);
        ans.push_back(dep[s[i]]+dep[t[i]]-mini);
    }
    return ans;
}

