#include "infection.h"
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

vector<int> adj[150005];

/*
int tin[150005];
int tout[150005];
int d[150005];
int timer = 0;
int up[150005][22];

void dfs(int x,int p=-1) {
    
    tin[x] = timer;
    timer++;
    if (p != -1) d[x] = d[p] + 1;
    else d[p] = 1;

    up[x][0] = p;
    for(int k=1;k<22;++k) {
        if (up[x][k-1] == -1) up[x][k] = -1;
        else up[x][k] = up[ up[x][k-1] ][k-1];
    }

    for(auto e:adj[x]) {
        if (e == p) continue;

        dfs(e,x);
    }

    tout[x] = timer;

    return;
}

bool anc(int a,int b) {
    return (tin[a] < tin[b] and tout[a] >= tout[b]);
}

int lca(int a,int b) {
    if (a == b) return a;
    if (anc(a,b)) return a;
    if (anc(b,a)) return b;

    for(int k=21;k>=0;k--) {
        if (up[a][k] != -1 and !anc(up[a][k],b)) {
            a = up[a][k];
        }
    }

    return up[a][0];
}

int path(int S,int T) {
    int l = lca(S,T);
    return d[S] + d[T] - d[l]*2;
}*/

vector<pair<int,int>> V[150005];
int cnt[50005];
bool ch = 0;

void dfs(int x,int id,int t,int d,int p=-1) {

    if (x == t) ch = 1;


    for(auto e:adj[x]) {
        if (e == p or ch) continue;

        dfs(e,id,t,d+1,x);
    }

    if (ch) {
        V[x].push_back({d,id});
    }

    return;
}


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 = (int)R.size() + 1;

    for(auto e:R) {
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);
    }

    int M = (int)D.size();

    vector<int> res(M,0);

    for(int i=0;i<M;++i) {
        ch = 0;
        dfs(S[i],i,T[i],D[i]);
    }

    for(int i=0;i<N;++i) {
        sort(V[i].begin(),V[i].end());
    }

    for(int t=0;t<=150000;++t) {
        for(int i=0;i<N;++i) {
            
            int cur = cnt[i];
            
            bool inf = 0;

            while (cur < (int)V[i].size() and V[i][cur].first == t) {
                int id = V[i][cur].second;
                if (I[id] or res[id] > 0) {
                    inf = 1;
                    break;
                }
                cur++;
            }

            cur = cnt[i];

            while (cur < (int)V[i].size() and V[i][cur].first == t) {
                int id = V[i][cur].second;
                if (inf) res[id]++;
                cur++;
            }
            cnt[i] = cur;
        }
    }

    

    return res;
}
