#include "infection.h"
#include <vector>
#include <utility>
#include <set>
using namespace std;

const int N = 200000 + 10;

vector<int> adj[N];

int ans[N], depth[N], up[N][20];
vector<set<int>> time(N);

void dfs0(int node, int parent) {
    up[node][0] = parent;
    for (int i = 1; i < 20; i++) {
        up[node][i] = up[up[node][i - 1]][i - 1];
    }
    for (auto i : adj[node]) {
        if (i == parent) continue;
        depth[i] = depth[node] + 1;
        dfs0(i, node);
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int d = depth[u] - depth[v];
    for (int i = 0; i < 20; i++) {
        if (d & (1 << i)) {
            u = up[u][i];
        }
    }
    if (u == v) return u;
    for (int i = 19; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

void get(int node, int parent, bool fl, int& timer) {
    if (!fl) {
        while (node != parent) {
            time[node].insert(timer);
            node = up[node][0];
            timer++;
        }
    }
    while (node != parent) {
        time[node].insert(timer);
        timer++;
        node = up[node][0];
    }
}

int get_time(int node, int parent, int t, bool fl) {
    int timer = t;
    while (node != parent) {
        if (time[node].count(t)) {
            return t;
        }
        node = up[node][0];
        if (!fl) t++;
        else t--;
    }
    return -1;
}

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) {
    for (auto e : R) {
        int u = e.first;
        int v = e.second;
        u++, v++;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs0(1, 1);
    vector<int> res;
    for (int i = 0; i < D.size(); i++) {
        if (!I[i]) continue;
        int lc = lca(S[i] + 1, T[i] + 1);
        int t = 0;
        get(S[i] + 1, lc, 0, t);
        get(T[i] + 1, lc, 1, t);
    }
    for (int i = 0; i < D.size(); i++) {
        int t = 0;
        int lc = lca(S[i] + 1, T[i] + 1);
        int get_l = get_time(S[i] + 1, lc, t, 0);
        int d = depth[S[i] + 1] + depth[T[i] + 1] - 2 * depth[lc];
        if (get_l != -1) {
            res.push_back(d - get_l + 1);
        }
        else {
            int get_r = get_time(T[i] + 1, lc, d, 1);
            if (get_r == -1) res.push_back(0);
            else res.push_back(d - get_r + 1);
        }
    }
    return res;
}
