#include "infection.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long


const int N = 5004;
vector<int> adj[N];
stack<int> rd[N];


bool dfs(int i, int p, int idx, int fn){
    if (i==fn){
        rd[idx].push(i); return 1;
    }
    for (int c: adj[i]){
        if (c==p) continue;
        if (dfs(c,i, idx, fn)){
            rd[idx].push(i);
            return 1;
        }
    }
    return 0;
}

std::vector<signed> solve(
    std::vector<std::pair<signed, signed>> R,
    std::vector<long long> D,
    std::vector<signed> S,
    std::vector<signed> T,
    std::vector<bool> I
){
    for (auto [u,v]: R){
        adj[u].push_back(v); adj[v].push_back(u);
    }
    int m = I.size(); 
    for (int i=0; i<m; i++){
        dfs(S[i], S[i], i, T[i]);
    }
    vector<int> fri(m, 1e18);
    vector<int> fint(m);
    for (int i=0; i<m; i++) fint[i] = D[i] + rd[i].size() - 1;
    for (int i=0; i<m; i++) if (I[i]) fri[i] = D[i];
    set<int> td;
    vector<int> inf(R.size() + 5,0);
    int tm = -1;
    map<int,vector<int>> tt; 
    set<int> te;
    for (int i=0; i<m; i++) tt[D[i]].push_back(i);
    while (1){
        if (td.size()) tm++; else {
            int mn = 1e18;
            for (int i=0; i<m; i++){
                if (D[i] > tm &&  D[i] < mn) {mn = D[i];}
            }
            if (mn > 1e17) break;
            tm = mn;
        }
        for (int i: tt[tm]){
            td.insert(i); if (I[i]) inf[S[i]]++;
        }
        for (int r: td){
            if (inf[rd[r].top()] && fri[r] > 1e17) inf[(rd[r].top())]++;
            if (inf[rd[r].top()]) fri[r] = min(fri[r], tm);
        }
        for (int r: td){
            if (fri[r] < 1e17) inf[rd[r].top()]--;;
            rd[r].pop();
            if (rd[r].empty()){
                te.insert(r); continue;
            }
            if (fri[r] < 1e17) inf[rd[r].top()]++;
        }
        for (int x: te) td.erase(x); te.clear();
    }
    vector<signed> res(m,0);
    for (int i=0; i<m; i++) res[i] = max(0ll, fint[i] - fri[i]+1);
    return res;
}
