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

using namespace std;

#define rep(i, a, b) for(int i = a; i <= b; i++)
#define pb push_back
#define F first
#define S second
#define pii pair<int, int>
#define ins insert

vector<int> solve(
    vector<pair<int, int>> R,
    vector<long long> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I
)
{
    int m = S.size();
    int n = R.size() + 1;
    vector<pair<pii, int>> x;
    rep(i, 0, m - 1){
        x.pb({{S[i], T[i]}, i});
    }
    sort(x.begin(), x.end());
    vector<int> adj[S.size() + 5];
    for(pii p : R){
        adj[p.F].pb(p.S);
        adj[p.S].pb(p.F);
    }
    vector<vector<int>> paths(m);
    rep(i, 0, m - 1){
        queue<pair<int, vector<int>>> q;
        q.push({S[i], {S[i]}});
        vector<int> pth;
        while(q.size()){
            int node = q.front().F;
            vector<int> path = q.front().S;
            q.pop();
            for(int to : adj[node]){
                if(path.size() == 1 || to != path[path.size() - 2]){
                    vector<int> pathh = path;
                    pathh.pb(to);
                    if(to == T[i]){pth = pathh; break;}
                    q.push({to, pathh});
                }
            }
            if(pth.size()) break;
        }
        paths[i] = pth;
    }
    /*
    rep(i, 0, m - 1){
        rep(j, 0, paths[i].size() - 1){
            cout << paths[i][j] << " ";
        }
        cout << '\n';
    }*/
    vector<vector<int>> grid(5005, vector<int>(5005, -1));
    rep(i, 0, m - 1){
        rep(j, 0, paths[i].size() - 1){
            grid[i][j + D[i]] = paths[i][j];
        }
    }
    /*
    rep(i, 0, m - 1){
        rep(j, 0, 20){
            cout << grid[i][j] << " ";
        }
        cout << '\n';
    }*/
    vector<int> ans(m);
    map<int, int> mp;
    rep(i, 0, m - 1){
        if(I[i]) mp[i] = D[i];
        else mp[i] = -1;
    }
    rep(j, 0, 5004){
        set<int> st;
        rep(i, 0, 5004){
            if(mp[i] != -1) st.ins(grid[i][j]);
        }
        rep(i, 0, 5004){
            if(st.find(grid[i][j]) != st.end()){
                if(mp[i] == -1) mp[i] = j;
            }
        }
    }
    rep(i, 0, m - 1){
        ans[i] = 0;
        if(mp[i] >= D[i]){
            ans[i] = paths[i].size() - (mp[i] - D[i]);
        }
        cout << i << " " << paths[i].size() << " " << mp[i] << " " << D[i] << '\n';
    }
    return ans;
}
