#include "infection.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 5005;
vector<int> g[N];
int up[N][15], lvl[N];

void dfs(int u, int p = 1) {
    up[u][0] = p;
    lvl[u] = lvl[p] + 1;
    for (int i = 1; i < 15; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for (int v : g[u]) {
        if (v == p) {
            continue;
        }
        dfs(v, u);
    }
}

int lca(int u, int v) {
    if (lvl[u] < lvl[v]) {
        swap(u, v);
    }
    for (int i = 14; i >= 0; i--) {
        if (lvl[up[u][i]] >= lvl[v]) {
            u = up[u][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = 14; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

int dis(int u, int v) {
    return lvl[u] + lvl[v] - 2 * lvl[lca(u, v)];
}

#undef int

vector<int> solve(vector<pair<int, int>> R, vector<long long> D, vector<int> S, vector<int> T, vector<bool> I) {

    vector<int> ans;
#define int long long

    int n = R.size() + 1;
    for (auto [u, v] : R) {
        u++, v++;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int m = D.size();
    ans.resize(m);
    dfs(1);
    for (int i = 0; i < m; i++) {
        if (I[i]) {
            ans[i] = dis(S[i] + 1, T[i] + 1);
        } else {
            ans[i] = 0;
        }
    }
    return ans;
}
