#include "infection.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> days[150005],adj[150005];
vector<int> ans;
bool dfs(int i,int dest,int par,int ind){
    // cout<<i<<' ';
    if(i==dest){
        days[ind].push_back(i);
        return 1;
    }
    for(int j:adj[i]){
        if(j!=par){
            if(dfs(j,dest,i,ind)){
                days[ind].push_back(i);
                return 1;
            }
        }
    }
    return 0;
}
vector<int> solve(
    vector<pair<int, int>> R,
    vector<long long> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I
){
    int n=R.size()+1,m=D.size();
    ans.assign(m,0);
    for(int i=0;i<n;i++) adj[i].clear();
    for(int i=0;i<m;i++) days[i].clear();
    for(pair<int,int>i:R){
        adj[i.first].push_back(i.second);
        adj[i.second].push_back(i.first);
    }
    for(int i=0;i<m;i++){
        dfs(S[i],T[i],0,i);
        reverse(days[i].begin(),days[i].end());
        // cout<<i<<'-';
        // for(int j:days[i]) cout<<j<<' ';
        // cout<<endl;
    }
    for(int i=0;i<=8005;i++){
        set<int>inf;
        for(int j=0;j<m;j++){
            if(days[j].size()>i){
                if(I[j]==1) inf.insert(days[j][i]);
            }
        }
        for(int j=0;j<m;j++){
            if(days[j].size()>i){
                if(inf.find(days[j][i])!=inf.end()) I[j]=1;
                if(I[j]==1) ans[j]++;
            }
        }
    }
    return ans;
}