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

 vector<int> solve(
    vector<pair<int, int>> R,
    vector<ll> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I) {
    int n=R.size()+1;
    int m=D.size();
    vector<int>ans(m,0);
    vector<vector<int>>adj(n);
    for (int i=0;i<n;i++) {
        adj[R[i].first].push_back(R[i].second);
        adj[R[i].second].push_back(R[i].first);
    }


    vector<vector<ll>>time(m,vector<ll>(n));
    vector<vector<int>>path(m,vector<int>(n));
    vector<int>distances(m);
    for (int i=0;i<m;i++) {
        queue<int>q;
        q.push(S[i]);
        time[i][S[i]]=D[i];
        vector<int>parent(n);
        vector<bool>visited(n,false);
        vector<int>dist(n);
        while (!q.empty()) {
            int node=q.front();
            q.pop();
            if (visited[node])
                continue;
            visited[node]=true;
            for (auto neighbour : adj[node]) {
                    if(!visited[neighbour]){
                    dist[neighbour]=dist[node]+1;
                    parent[neighbour]=node;
                    q.push(neighbour);
                }
            }
        }
        int end_node=T[i];
        distances[i]=dist[end_node];
        time[i][end_node]=D[i]+dist[end_node];
        while (parent[end_node]!=S[i]) {
            path[i][parent[end_node]]=end_node;
            //cout << parent[end_node] << endl;
            time[i][parent[end_node]]=D[i]+dist[parent[end_node]];
            end_node=parent[end_node];
        }
        path[i][parent[end_node]]=end_node;
    }
    /*for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout << time[j][i] << " ";
        }
        cout << endl;
    }*/
    priority_queue<pair<int,pair<ll,int>>,vector<pair<int,pair<ll,int>>>,greater<pair<int,pair<ll,int>>>>infected;
    for(int i=0;i<m;i++){
        if(I[i])
            infected.push({D[i],{S[i],i}});
    }
    set<int>inf;
    /*for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cout << path[i][j] << " ";
        }
        cout << endl;
    }
    */
    while(!infected.empty()){
        int node=infected.top().second.first;
        int index=infected.top().second.second;
        ll day= infected.top().first;
        inf.insert(index);
        ans[index]=day;
        infected.pop();
        ll cnt=0;
        while(path[index][node]!=T[index]){
            for(int idx=0;idx<m;idx++){
                if(time[index][node]==time[idx][node]){
                    if(!inf.count(idx)){
                        infected.push({time[index][node],{S[idx],idx}});
                        inf.insert(idx);
                    }
                }
            }
            //cout << node << endl;
            node=path[index][node];
            cnt++;
        }
        //cout << node<< endl;
        for(int idx=0;idx<m;idx++){
                //cout << time[idx][node] << " ";
                if(time[index][node]==time[idx][node]){
                    if(!inf.count(idx)){
                        //cout << "YES";
                       infected.push({time[index][node],{S[idx],idx}});
                        inf.insert(idx);
                    }
                }
            }
        //cout << endl;
        node=path[index][node];
        cnt++;
        //cout << node << " " << day+cnt<<  endl;
        for(int idx=0;idx<m;idx++){
                if(time[index][node]==time[idx][node]){
                    if(!inf.count(idx)){
                        infected.push({time[index][node],{S[idx],idx}});
                        inf.insert(idx);
                    }
                }
            }
    }
    for(int i=0;i<m;i++){
        if(ans[i]!=0){
            ll diff=ans[i]-D[i];
            ans[i]=distances[i]-diff+1;
        }
    }
    return ans;
}