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

#define f first
#define s second
#define pb push_back
#define elif else if
#define nl '\n'

#pragma GCC optimize("O3,unroll-loops")
#pragma target("avx2,bmi,bmi2,pop_cnt,lz_cnt")

#define long int64_t

using namespace std;

const int N = 1.5e5 + 9;

int n, m;
vector <int> g[N];

vector<int> solve(
    vector<pair<int, int>> R,
    vector<long> tme,
    vector<int> s,
    vector<int> f,
    vector<bool> b
) {
    n = R.size() + 1;
    m = tme.size();
    for (int i = 0; i < n - 1; ++i) {
        g[R[i].f].pb(R[i].s);
        g[R[i].s].pb(R[i].f);
    }
    long ent[m];
    vector <array <long, 3>> all;
    for (int i = 0; i < m; ++i) {
        int from[n];
        fill(from, from + n, -1);
        queue <int> q;
        from[s[i]] = s[i];
        q.push(s[i]);
        while (q.size()) {
            int p = q.front();
            q.pop();
            for (int u : g[p])
                if (from[u] == -1) {
                    from[u] = p;
                    q.push(u);
                }
        }
//        cout << i << ": ";
        vector <int> v;
        for (int j = f[i]; j != s[i]; j = from[j])
            v.pb(j);
        v.pb(s[i]);
        reverse(v.begin(), v.end());
//        for (int u : v)
//            cout << u << " ";
//        cout << nl;
        ent[i] = tme[i] + v.size();
        for (int j = 0; j < v.size(); ++j)
            all.pb({tme[i] + j, v[j], i});
    }
    sort(all.begin(), all.end());
    long mn[m];
    fill(mn, mn + m, long(1e18));
    for (int i = 0; i < all.size();) {
        int j = i;
        while (j < all.size() && all[j][0] == all[i][0] && all[j][1] == all[i][1])
            ++j;
        bool inf = 0;
        for (int k = i; k < j; ++k)
            inf |= b[all[k][2]];
        if (inf)
            for (int k = i; k < j; ++k) {
                b[all[k][2]] = 1;
                mn[all[k][2]] = min(mn[all[k][2]], all[k][0]);
            }
        i = j;
    }
    vector <int> ans(m);
    for (int i = 0; i < m; ++i)
        if (b[i])
            ans[i] = ent[i] - mn[i];
    for (int i = 0; i < n; ++i)
        g[i].clear();
    return ans;
}

#undef long
