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

vector<vector<int>> adj;

vector<bool> f;

struct dsu{
    vector<int> sz,p;
    int n;
    dsu(int _n){
        n = _n;
        sz.assign(_n,1);
        p.resize(_n);
        iota(p.begin(),p.end(),0);
    }
    int find(int x){
        if(p[x] == x) return p[x];
        return p[x] = find(p[x]);
    }
    bool merge(int a, int b){
        int x = find(a);
        int y = find(b);
        if(!f[x] and !f[y]) return false;
        if(x == y) return false;
        if(sz[x] < sz[y]) swap(x,y);
        f[x] = f[y] = true;
        sz[x] += sz[y];
        p[y] = p[x];
        return true;
    }
};

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
) {
    int n = R.size()+1;
    int m = D.size();

    adj.resize(n);
    for(auto &[u,v] : R){
        adj[v].emplace_back(u);
        adj[u].emplace_back(v);
    }

    vector<queue<int>> path(m);
    vector<int> init(m);

    for(int i = 0; i < m; ++i) {
        queue<int> q;
        q.push(S[i]);
        vector<bool> vis(n,false);
        vector<int> p(n,-1);
        vis[S[i]] = true;
        while(!q.empty()){
            int t = q.front();
            q.pop();
            vis[t] = true;

            for(auto u : adj[t]){
                if(!vis[u]){
                    q.push(u);
                    p[u] = t;
                    if(u == T[i]) break;
                }
            }
        }
        int C = T[i];
        vector<int> ret;
        while(C != S[i]){
            ret.push_back(C);
            C = p[C];
        }
        reverse(ret.begin(),ret.end());
        for(auto &j : ret)path[i].push(j);
        init[i] = ret.size()+1;
        //cerr<<path[i].size()<<endl;
    }

    vector<int> ind(m);
    iota(ind.begin(),ind.end(),0);

    sort(ind.begin(),ind.end(),[&](int x, int y){
        return D[x] < D[y];
    });

    for(int i = 1; i < ind.size(); ++i){
        D[i] = min(D[i], D[i-1]+init[i-1]);
    }
    int off = D[0];


    int MAXT = D[m-1]+init[m-1];

    int time = 0;

    dsu d(m+1);
    int ff = -1;
    vector<int> in(m,-1);
    for(int i = 0; i < m; ++i){
        if(I[i]) {
            ff = i;
        }
    }

    if(ff == -1){
        vector<int> RE(m,0);
        return RE;
    }
    f.resize(m,false);
    f[ff]= true;
    for(int i = 0; i < m; ++i){
        if(I[i]){
            d.merge(i,ff);
            f[i] = true;
            in[i] = 0;
        }
    }

    {

        map<int,vector<int>> idx;
        for(int i = 0; i < m; ++i){
            if(time>=D[i]){
                idx[S[i]].emplace_back(i);
            }
            //cerr<<S[i]<<endl;
        }
        bool flag = false;
        for(auto &[u, vec]: idx){
            for(auto &p : vec){
                if(f[p]) {
                    for(auto &q: vec){
                        if(d.merge(q,p)){
                            in[q] = time;
                            f[q] = true;
                        }
                    }
                    flag=true;
                    break;
                }
            }
        }

    }
    for(int j = 0; j <= MAXT; ++j) {
        ++time;
        map<int,vector<int>> idx;
        for(int i = 0; i < m; ++i){
            if(path[i].empty() or D[i]>time) continue;

            if(time>D[i]){
                S[i] = path[i].front();
                path[i].pop();
            }
            idx[S[i]].emplace_back(i);
            //cerr<<S[i]<<endl;
        }

        bool flag = false;
        for(auto &[u, vec]: idx){
            for(auto &p : vec){
                if(f[p]) {
                    for(auto &q: vec){
                        if(d.merge(q,p)){
                            in[q] = time;
                            f[q] = true;
                        }
                    }
                    flag=true;
                    break;
                }
            }
        }
    }

    vector<int> ans(m);
    for(int i = 0; i < m; ++i){
            //cerr<<D[i]<<" ";
        if(in[i]==-1){
            if(I[i])ans[i]=init[i];
            else ans[i]=0;
        }else{
            ans[i]=init[i]-in[i];
        }
        //ans[i]=in[i];
    }
    return ans;
}