#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n,m;
 vector<int> solve(
    vector<pair<int, int>> R,
    vector<ll> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I) {
    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,-1));
    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;
    }
    map<pair<ll,int>,queue<int>>same;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(time[j][i]!=-1){
                same[{time[j][i],i}].push(j);
                //cout << "time: " << time[j][i] << " city: " << i << " vip: " << j << endl;
            }
        }
    }
    queue<pair<int,pair<ll,int>>>infected;
    for(int i=0;i<m;i++){
        if(I[i])
            infected.push({S[i],{D[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.front().first;
        int index=infected.front().second.second;
        ll day= infected.front().second.first;
        inf.insert(index);
        ans[index]=day;
        infected.pop();
        ll cnt=0;
        while(path[index][node]!=T[index]){
            while(!same[{day+cnt,node}].empty()){
                if(!inf.count(same[{day+cnt,node}].front()))
                    infected.push({node,{day+cnt,same[{(ll)(day+cnt),node}].front()}});
                same[{day+cnt,node}].pop();
            }
            // << node << endl;
            node=path[index][node];
            cnt++;
        }
       // cout << node << endl;
        while(!same[{day+cnt,node}].empty()){
                if(!inf.count(same[{day+cnt,node}].front()))
                    infected.push({node,{day+cnt,same[{(ll)(day+cnt),node}].front()}});
                same[{day+cnt,node}].pop();
        }
       // cout << node << endl;
        node=path[index][node];
        cnt++;
        while(!same[{day+cnt,node}].empty()){
                if(!inf.count(same[{day+cnt,node}].front()))
                    infected.push({node,{day+cnt,same[{(ll)(day+cnt),node}].front()}});
                same[{day+cnt,node}].pop();
        }
    }
    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;
}