#include "infection.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>

using namespace std;
using ll = long long;
const int NMAX = 150000;
const int LOG = 18; ///2^17 max

vector <vector <int>> v;
int n, m;

int tata[NMAX + 2];
int depth[NMAX + 2];
int up[LOG + 1][NMAX + 2];

void dfs(int start) { ///e mai mult pt build
    for(auto nod : v[start]) {
        if(nod == tata[start])
            continue;
        tata[nod] = start;
        depth[nod] = depth[start] + 1;
        up[0][nod] = start;
        for(int j = 1; j < LOG; j++)
            up[j][nod] = up[j - 1][up[j - 1][nod]];
        dfs(nod);
    }
}

int LCA(int a, int b) {
    if(depth[a] < depth[b])
        swap(a, b);
    int k = depth[a] - depth[b];
    for(int j = LOG - 1; j >= 0; j--) {
        if(k & (1 << j))
            a = up[j][a];
    }
    if(a == b)
        return a;
    for(int j = LOG - 1; j >= 0; j--) {
        if(up[j][a] != up[j][b]) {
            a = up[j][a];
            b = up[j][b];
        }
    }
    return up[0][a];
}
int buildDrum(int a, int b) {
    int lca = LCA(a, b);
    return depth[a] - depth[lca] + depth[b] - depth[lca] + 1;
}
vector<int> solve( vector<pair<int, int>> R, vector<ll> D, vector<int> S, vector<int> T,vector<bool> I) {
    ///Indexam de la 1 ca asa ne PLACE!!
    for(auto& var : R) {
        var.first++;
        var.second++;
    }
    for(auto &var : S)
        var++;
    for(auto& var: T)
        var++;

    ///resetam TOT
    n = R.size() + 1;
    v.clear();
    v.resize(n + 1);
    for(int i = 1; i <= n; i++) {
        tata[i] = 0;
        depth[i] = 0;
    }
    m = D.size();

    for(auto var : R) {
        v[var.first].push_back(var.second);
        v[var.second].push_back(var.first);
    }
    dfs(1);
    vector <int> ans;
    ///Dam build la TOATE drumurile
    for(int i = 1; i <= m; i++) {
        if(!I[i - 1])
            ans.push_back(0);
        else {
            ans.push_back(buildDrum(S[i - 1], T[i - 1]));
        }
    }
    return ans;
}