#include <iostream>
#include<vector>
#include<utility>
#include<algorithm>


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
    ){
    long long n=R.size()+1,m=D.size();
    std::vector<long long>R1[n];
    for(long long i=0;i<R.size();i++){
        R1[R[i].first].push_back(R[i].second);
        R1[R[i].second].push_back(R[i].first);
    }
    std::vector<long long>put[m];
    long long place;
    for(long long i=0;i<m;i++){
        std::vector<long long> cities(n,0);
        cities[S[i]]=1;
        for(long long j=1;j<n;j++){
            for(long long k=0;k<n;k++){
                if(cities[k]==j){
                    for(long long q=0;q<R1[k].size();q++){
                        if(cities[R1[k][q]]==0){
                            cities[R1[k][q]]=j+1;
                        }
                    }
                }
            }
            if(cities[T[i]]>0){
                break;
            }
        }
        place=T[i];
        for(long long j=cities[T[i]];j>=1;j--){
            put[i].push_back(place);
            for(long long k=0;k<R1[place].size();k++){
                if(cities[R1[place][k]]==j-1){
                    place=R1[place][k];
                    break;
                }
            }
        }
        reverse(put[i].begin(),put[i].end());
    }
    std::vector<int>broiach(m,0);
    long long longestput=0;
    for(long long i=0;i<m;i++){
        if(longestput<D[i]+put[i].size())longestput=D[i]+put[i].size();
    }
    std::vector<long long>position(m,0);
    std::vector<long long>stupka(m,0);
    long long rest,closest,who;
    for(long long i=0;i<longestput;i++){
        rest=0;
        for(long long j=0;j<m;j++){
            if(D[j]==i){
                position[j]=put[j][0];
                stupka[j]++;
            }else if(D[j]<i&&put[j].size()>stupka[j]){
                position[j]=put[j][stupka[j]];
                stupka[j]++;
            }else if(put[j].size()==stupka[j]){
                stupka[j]++;
            }else{
                rest++;
            }
        }
        if(rest==m){
            closest=0;
            for(long long j=0;j<m;j++){
                if(D[j]>i&&(closest==0||closest>D[j])){
                    closest=D[j];
                }
            }
            i=closest-1;
        }else if(rest==m-1){
            closest=0;
            for(long long j=0;j<m;j++){
                if(stupka[j]<=put[j].size()&&D[j]<=i){
                    who=j;
                }else if(D[j]>i&&(closest==0||closest>D[j])){
                    closest=D[j];
                }
            }
            if(I[who]==false){
                if(closest>0)i=closest-1;
                else i=longestput;
                stupka[who]+=closest-i;
            }else{
                if(closest>0){
                    broiach[who]+=closest-i;
                    i=closest-1;
                }else{
                    broiach[who]+=longestput-i;
                    i=longestput;
                }
                stupka[who]+=closest-i;
            }
        }else{
            for(long long j=0;j<m;j++){
                if(put[j].size()>=stupka[j]&&D[j]<=i&&I[j]){
                    for(long long k=0;k<m;k++){
                        if(put[k].size()>=stupka[k]&&D[k]<=i){
                            if(position[j]==position[k])I[k]=true;
                        }
                    }
                }
            }
            for(long long j=0;j<m;j++){
                if(I[j]&&put[j].size()>=stupka[j]&&D[j]<=i)broiach[j]++;
            }
        }
    }
    return broiach;
}