#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);
    }
    vector<pair<ll, int>> pos(m);
    for (int i = 0; i < m; ++i) {
        pos[i] = { d[i],i };
    }
    sort(pos.begin(), pos.end());
    vector<ll> newd(m);
    vector<int> news(m);
    vector<int> newt(m);
    vector<bool> newI(m);
    for (int i = 0; i < m; ++i) {
        newd[i] = d[pos[i].second];
        news[i] = s[pos[i].second];
        newt[i] = t[pos[i].second];
        newI[i] = I[pos[i].second];
    }
    d = newd;
    s = news;
    t = newt;
    I = newI;
    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 < m; ++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;
                    vis[j] = 1;
                }
                else {
                    break;
                }
            }
            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-1;
                        break;
                    }
                }
            }
        }
    }
    vector<int> new_answ = answ;
    for (int i = 0; i < m; ++i) {
        new_answ[pos[i].second] = answ[i];
    }
    return new_answ;
}
int main()
{
    vector<pair<int, int>> r = { {0,1},{1,2},{2,3},{3,4},{4,5},{3,6},{6,7},{6,8} };
    vector<int> s={0,5,5,7,0};
    vector<int> t = {5,7,7,8,1};
    vector<long long > d = {1,3,4,8,10};
    vector<bool> I = {1,0,0,0,0};
    vector<int> answ = solve(r,d,s,t,I);
    for (auto i : answ) {
        cout << i << ' ';
    }
    return 0;
}