#include "infection.h"
#include <vector>
#include <utility>
#include "bits/stdc++.h"

using namespace std;

const int mxn=5020;

vector<int>aj[mxn];
vector<pair<int,long long>>path;
bool ok;

// map<long long,map<int,vector<int>>>mp;
vector<int> mp[10020][5020];
vector<long long> t;

void dfs(int i,int p,int u,int f,long long d,bool s){
    path.emplace_back(u,d);
    if(u == f&&!ok){
        ok = true;
        for(auto p:path){
            if(s) {
                int tim = lower_bound(begin(t),end(t),p.second)-begin(t);
                mp[tim][p.first].push_back(i);
            } else t.push_back(p.second);
        }
        return;
    }
    for(int v : aj[u])if(v!=p&&!ok)
        dfs(i,u,v,f,d+1,s);
    path.pop_back();
}

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
) {
    for(auto eg:R){
        aj[eg.first].push_back(eg.second);
        aj[eg.second].push_back(eg.first);
    }
    int m=D.size();
    for(int i = 0; i < m; i ++){
        ok = false;
        path.clear();
        dfs(i,-1,S[i],T[i],D[i],false);
    }
    sort(begin(t),end(t));
    t.erase(unique(begin(t),end(t)),end(t));
    for(int i = 0; i < m; i ++){
        ok = false;
        path.clear();
        dfs(i,-1,S[i],T[i],D[i],true);
    }
    vector<int>ans(m);
    for(int i = 0; i < t.size(); i ++){
        for(int j = 0; j < 5020; j ++){
            bool inf=false;
            for(auto k : mp[i][j])
                if(I[k])inf = true;
            for(auto k : mp[i][j]){
                I[k]=I[k] or inf;
                if(I[k])ans[k]++;
            }
        }
    }
    return ans;
}
