#include <bits/stdc++.h>
using namespace std;
vector <int> v[150005];
int d[150005], s[150005], t[150005], inf[150005];
int m, n;
int used[150005];
int depth[150005];
int par[150005];
void dfs(int beg)
{
    used[beg] = 1;
    for(int i = 0; i < v[beg].size(); i++)
    {
        if(!used[v[beg][i]])
        {
            depth[v[beg][i]] = depth[beg]+1;
            ///cout << beg << " " << v[beg][i] << " " << depth[v[beg][i]] << endl;
            par[v[beg][i]] = beg;
            used[v[beg][i]] = 1;
            dfs(v[beg][i]);
        }
    }
}
int bin_lift[150005][16];
void fill_bl()
{
    for(int i = 0; i < log(n)+1; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(i == 0)bin_lift[j][i] = par[j];
            else bin_lift[j][i] = bin_lift[bin_lift[j][i-1]][i-1];
        }
    }
}
int bin_search(int x, int y)
{
    int l = 0, r = log(n);
    while(l <= r)
    {
        int mid = (l+r)/2;
        if(bin_lift[x][mid] == bin_lift[y][mid])r = mid-1;
        else l = mid+1;
    }
    return r;
}
int lca(int x, int y)
{
    while(depth[x] != depth[y])
    {
        if(depth[x] > depth[y])x = par[x];
        else y = par[y];
    }
    if(x == y)return x;
    while(x == y)
    {
        int c = bin_search(x, y);
        if(c == -1)return par[x];
        else
        {
            x = bin_lift[x][c];
            y = bin_lift[y][c];
        }
    }
    return x;
}
std::vector<int> solve(std::vector<std::pair<int, int>> R, std::vector<long long> D, std::vector<int> S, std::vector<int> T, std::vector<bool> I)
{
    for(int i = 0; i < R.size(); i++)
    {
        v[R[i].first+1].push_back(R[i].second+1);
        v[R[i].second+1].push_back(R[i].first+1);
        n = max(n, R[i].first+1);
        n = max(n, R[i].second+1);
    }
    m = D.size();
    for(int i = 0; i < m; i++)
    {
        d[i+1] = D[i];
        s[i+1] = S[i]+1;
        t[i+1] = T[i]+1;
        inf[i+1] = I[i];
    }
    depth[1] = 1;
    dfs(1);
    vector <int> ans;
    for(int i = 0; i < m; i++)
        ans.push_back(0);
    for(int i = 1; i <= m; i++)
    {
        if(inf[i] == 0)ans[i-1] = 0;
        else
        {
            int c = lca(s[i], t[i]);
            ///cout << depth[s[i]] << " " << depth[t[i]] << " " << depth[c] << endl;
            ans[i-1] = depth[s[i]] + depth[t[i]] - depth[c];
        }
    }
    return ans;
}
