#include "bits/stdc++.h"
#include "infection.h"
// #include "grader.cpp"
using namespace std;

const int inf = INT_MAX;

#define N 200005

long long n, m, ok = 0, nod[N];
vector<int> E[N], ans, v, P[N];
set <int> F[N], f;

void solve(int nd,int en,int par) {
    v.push_back(nd);
    if(en == nd) ok = 1;
    if(ok) return;
    for(auto i : E[nd]) {
        if(i == par) continue;
        solve(i, en, nd);
        if(ok) return;
    }
    if(ok) return;
    v.pop_back();
}

vector<int> solve(vector<pair<int, int>> R, vector<long long> D,vector<int> S,vector<int> T,vector<bool> I) {
    n = (int)R.size();
    m = (int)D.size();
    ans.resize(m, 0);
    for(int i = 0; i < n; i++) {
        E[i].clear();
        nod[i] = 0;
        P[i].clear();
    }
    for(int i = 0; i < n; i++) {
        E[R[i].first].push_back(R[i].second);
        E[R[i].second].push_back(R[i].first);
    }
    for(int i = 0; i < m; i++) {
        ok = 0;
        v.clear();
        solve(S[i], T[i], -1);
        nod[i] = S[i];
        for(auto j : v) {
            P[i].push_back(j);
        }
    }
    for(int i = 0; i < n; i++) {
        vector <pair <int,int>> pp = {};
        f.clear();
        for(int j = 0; j < m; j++) {
            if(i >= (int)P[j].size()) continue;
            nod[j] = P[j][i];
            if(I[j]) {
                ans[j]++;
                f.insert(nod[j]);
            }
            else {
                pp.push_back({nod[j], j});
            }
        }
        for(auto j : pp) {
            if(f.find(j.first) != f.end()) {
                I[j.second] = 1;
                ans[j.second]++;
            }
        }
    }
    return ans;
}
