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

using namespace std;

const int mxn=5020;

vector<int>path[mxn];
vector<int>aj[mxn];
bool ok;
int n;

void dfs(int i,int p,int u,int f){
    path[i].emplace_back(u);
    n=max(n,u);
    if(u == f&&!ok){
        ok = true;
        return;
    }
    for(int v : aj[u])if(v!=p&&!ok)
        dfs(i,u,v,f);
    if(!ok)path[i].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;
        dfs(i,-1,S[i],T[i]);
    }
    vector<bool>alive(m,true);
    vector<int>at(m);
    vector<bool>new_inf(n);
    vector<int>ans(m);
    int c = 0;
    while (true){
        vector<int>mns;
        int mn=INT_MAX;
        for(int i = 0; i < m; i ++){
            if(alive[i] and D[i] < mn){
                mn = D[i];
                mns.clear();
                mns.push_back(i);
            }else if (D[i]<=mn)
                mns.push_back(i);
        }
        for (int i : mns)
            D[i]++;
        for(int i : mns) {
            bool f = new_inf[path[i][at[i]]];
            new_inf[path[i][at[i]]] = f or I[i];
        }
        for(int i : mns)
            if (new_inf[path[i][at[i]]])
                I[i]=true;
        for(int i = 0; i < m; i ++)
            if(alive[i] and I[i])
                ans[i]++;
        for (int i : mns)
            new_inf[path[i][at[i]]]=false;
        for(int i : mns)
            if(at[i]==(int)path[i].size()-1)
                alive[i]=false,c++;
            else at[i]++;
        if(c==m)break;
        // cout<<"hey "<<c<<endl;
        // for (int i : D)
        //     cout<<i<<' ';
        // cout<<endl;
        // for(int i : I)
        //     cout<<i<<' ';
        // cout<<endl;
        // for(int i : alive)
        //     cout<<i<<' ';
        // cout<<endl;
        // cout<<endl;
    }
    return ans;
}
