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

const int N = 200000 + 10;

vector<int> adj[N];

int ans[N], depth[N], up[N][20];
bool marked[5005][5005];

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, int D, bool fl) {
    if (!fl) {
        int timer = 0;
        while (node != parent) {
            marked[node][timer] = 1;
            node = up[node][0];
            timer++;
        }
        marked[node][timer] = 1;
        return;
    }
    int timer = D;
    while (node != parent) {
        marked[node][timer] = 1;
        node = up[node][0];
        timer--;
    }
}

void travel(int node, int parent, int val, int D, bool fl) {
    if (!fl) {
        int timer = 0;
        while (node != parent) {
            if (marked[node][timer]) val = 1;
            marked[node][timer] = val;
            timer++;
            node = up[node][0];
        }
        marked[node][timer] = val;
        return;
    }
    int timer = 0;
    vector<int> v;
    while (node != parent) {
        v.push_back(node);
        timer--;
        node = up[node][0];
    }
    v.push_back(node);
    reverse(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++) {
        int u = v[i];
        if (marked[u][timer]) val = 1;
        marked[u][timer] = val;
        timer++;
    }
}

int get_time(int node, int parent, int D, bool fl) {
    if (!fl) {
        int timer = 0;
        while (node != parent) {
            if (marked[node][timer]) {
                return timer;
            }
            node = up[node][0];
            timer++;
        }
        if (marked[node][timer]) return timer;
        return -1;
    }
    int timer = 0;
    vector<int> v;
    while (node != parent) {
        v.push_back(node);
        timer--;
        node = up[node][0];
    }
    v.push_back(node);
    reverse(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++) {
        int u = v[i];
        if (marked[u][timer]) {
            return timer;
        }
        timer++;
    }
    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, d = depth[S[i] + 1] + depth[T[i] + 1] - 2*depth[lc] + 1;
        get(S[i] + 1, lc, 0, 0);
        get(T[i] + 1, lc, d, 1);
    }
    for (int i = 0; i < D.size(); i++) {
        if (I[i]) continue;
        int lc = lca(S[i] + 1, T[i] + 1);
        int d = depth[S[i] + 1] + depth[T[i] + 1] - 2 * depth[lc] + 1;
        travel(S[i] + 1, lc, 0, 0, 0);
        travel(T[i] + 1, lc, 0, d, 1);
    }
    for (int i = 0; i < D.size(); i++) {
        int lc = lca(S[i] + 1, T[i] + 1);
        int d = depth[S[i] + 1] + depth[T[i] + 1] - 2 * depth[lc] + 1;
        int get_l = get_time(S[i] + 1, lc, 0, 0);
        if (get_l == -1) {
            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);
            }
        }
        else {
            res.push_back(d - get_l);
        }
    }
    return res;
}
