#include "infection.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 150000;

vector<int> g[NMAX + 3];
vector<int> lvl(NMAX + 3, 0);
int t[NMAX + 3][25];
int dfsin[NMAX + 3], dfsout[NMAX + 3];

//int walk[NMAX + 3][NMAX + 3];

int n, m;

void solve5() {
    //lant
}

void solve12() {
    //brute
}

void solve4() {
    //dist de la s la t daca i e 1
}

bool isancestor(int u, int v) { //e u stramos de v
    return dfsin[u] <= dfsin[v] && dfsout[u] >= dfsout[v];
}

int lca(int x, int y) {
    if(lvl[x] > lvl[y])
        swap(x, y);

    if(isancestor(x, y))
        return x;

    for(int put = 24; put >= 0; put--) {
        if(!isancestor(t[x][put], y))
            x = t[x][put];
    }

    return t[x][0];
}

void rmq() {
    for(int node = 0; node < n; node++) {
        for(int put = 1; put < 25; put++) {
            t[node][put] = t[t[node][put - 1]][put - 1];
        }
    }
}

int timp = 0;

int dist(int x, int y) {
    int l = lca(x, y);
    return lvl[x] - lvl[l] + lvl[y] - lvl[l];
}

void dfs(int node) {
    dfsin[node] = ++timp;

//    cout<<"d "<<node<<" "<<lvl[node]<<"\n";

    for(int nxnode : g[node]) {
        if(lvl[nxnode] == 0) {
            lvl[nxnode] = lvl[node] + 1;
            t[nxnode][0] = node;
            dfs(nxnode);
        }
    }

    dfsout[node] = ++timp;
}

void calc() {
    lvl[0] = 1;
    dfs(0);
    rmq();

//    for(int i = 0; i < n; i++)
//        for(int j = 0; j < n; j++)
//            cout << lca(i, j) << " " << i << " " << j << "\n";
}

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
) {
    n = R.size() + 1;
    m = D.size();

//    cout << n << " " << m << "\n";

    vector<int> ans(m, 0);

    for(pair<int, int> pii : R) {
        g[pii.first].push_back(pii.second);
        g[pii.second].push_back(pii.first);
    }

    calc();

    for(int i = 0; i < m; i++) {
        if(I[i] == 1)
            ans[i] = dist(S[i], T[i]) + 1;
    }

    return ans;
}
