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

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> g[150005];
int p[20][150005];
int nivel[150005];

void dfs(int node, int parent) {
    p[0][node] = parent;
    for(int bit = 1; (nivel[node] - (1 << bit)) >= 0; bit++) {
        p[bit][node] = p[bit - 1][p[bit - 1][node]];
    }
    for(auto nxt : g[node]) {
        if(nxt != parent) {
            nivel[nxt] = nivel[node] + 1;
            dfs(nxt, node);
        }
    }
}

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
) {
    // fac un bfs din fiecare om ca sa imi fac un arbore rootat in el
    // fiecare om o sa faca maxim 5000 de pasi deci pot sa simulez efectiv?
    // dau skip cat timp nu am pe nimeni
    n = R.size() + 1;
    m = D.size();

    vector<int> ans(m, 0);

    for(auto e : R) {
        g[e.first].push_back(e.second);
        g[e.second].push_back(e.first);
    }
    
    // pt subtask 4 pot sa calculez doar lungimea drumului si o sa fie 
    // lg daca I[i] = 1, altfel 0

    // trb sa fac lca

    for(int i = 0; i <= 19; i++) {
        for(int j = 0; j <= m; j++) {
            p[i][j] = -1;
            nivel[j] = 0;
        }
    }

    dfs(0, -1);
    for(int i = 0; i < m; i++) {
        if(I[i] == 0) continue;
        // fac lca intre S[i] si T[i];
        int s = S[i], t = T[i];
        if(nivel[s] < nivel[t]) swap(s, t);
        for(int bit = 20; bit >= 0; bit--) {
            if(nivel[s] - (1 << bit) >= nivel[t]) {
                s = p[bit][s];
            }
        }
        // sunt la acelasi nivel
        // caut lca si nivel lca

        // cout << s << ' ' << nivel[s] << ' ' << t << ' ' << nivel[t] << '\n';

        if(s == t) {
            ans[i] = abs(nivel[S[i]] - nivel[T[i]]) + 1;
            continue;
        }
        for(int bit = 19; bit >= 0; bit--) {
            if(p[bit][s] >= 0 && p[bit][t] >= 0 && p[bit][s] != p[bit][t]) {
                // cout << bit << ' ' << s << ' ' << t << ' ' << p[bit][s] << ' ' << p[bit][t] << '\n';
                s = p[bit][s];
                t = p[bit][t];
            }
        }
        s = p[0][s]; t = p[0][t];
        // cout << i << ' ' << S[i] << ' ' << nivel[S[i]] << ' ' << T[i] << ' ' << nivel[T[i]] << ' ' << s << ' ' << nivel[s] << ' ' << t << ' ' << nivel[t] << '\n';
        ans[i] = (abs(nivel[s] - nivel[S[i]]) + 1) + (abs(nivel[s] - nivel[S[i]]) + 1) - 1;
    }

    return ans;
}
