#include "infection.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
#define ll long long
const int N = 3e5 + 1;
vector<int> g[N];
bool vis[N];
int p[N];
void dfs(int v,int x) {
    p[v] = x;
    for (auto i : g[v]) {
        if (i != x) {
            dfs(i, v);
        }
    }
}
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
) {
    int n = r.size() + 1;
    int m = d.size();
    vector<queue<int>> nxt(m);
    vector<int> answ(m,0);
    vector<int> varak(n+1,0);
    for (auto i : r) {
        g[i.first].push_back(i.second);
        g[i.second].push_back(i.first);
    }
    for (int i = 0; i < m; ++i) {
        dfs(s[i],-1);
        int x = t[i];
        vector<int> o;
        while (x != s[i]) {
            o.push_back(x);
            x = p[x];
        }
        o.push_back(s[i]);
        reverse(o.begin(), o.end());
        for (auto j : o) {
            nxt[i].push(j);
        }
    }
    for (int i = 0; i < 1; ++i) {
        if (!vis[i]) {
            ll time = d[i];
            queue<int> q;
            int val = i;
            for (int j = i; j < m; ++j) {
                if (d[i] == d[j]) {
                    q.push(j);
                    val = j;
                }
            }
            vector<int> tex;
            vector<int> k;
            while (!q.empty()) {
                k.clear();
                tex.clear();
                while (!q.empty()) {
                    int f = q.front();
                    tex.push_back(nxt[f].front());
                    if (I[f])
                        varak[nxt[f].front()] = 1;
                    q.pop();
                    k.push_back(f);
                }
                for (auto i : k) {
                    if (varak[nxt[i].front()]) {
                        I[i] = 1;
                        answ[i]++;
                    }
                }
                for (auto i : tex) {
                    varak[i] = 0;
                }
                for (auto i : k) {
                    nxt[i].pop();
                    if (!nxt[i].empty()) {
                        q.push(i);
                    }
                }
                time++;
                for (int j = val + 1; j < m; ++j) {
                    if (time == d[j]) {
                        q.push(j);
                        vis[j] = 1;
                        if (j == m - 1) {
                            val = m-1;
                        }
                    }
                    else {
                        val = j;
                    }
                }
            }
        }
    }
    return answ;
}