#include "infection.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size()
#define eb emplace_back
#define deb(x) cout << #x << " " << x << endl

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
) {
    int n = -1;
    for (auto [a,b]:R) {
        n = max({n,a+1,b+1});
    }
    vector <vector<int>> v(n+1);
    for (auto [a,b]:R) {
        v[a+1].eb(b+1);
        v[b+1].eb(a+1);
    }

    vector <int> in(n+1);
    vector <int> out(n+1);
    vector <vector<int>> up(n+5,vector<int>(25,0));
    int timer = 0;
    vector <int> d(n+1);
    auto dfs = [&](auto self, int x, int p) -> void {
        // deb(1);

        in[x] = ++timer; 
        up[x][0] = p;
        for (int i = 1; i <= 20; i++) {
            // deb(i);
            // deb(x);
            // deb(up[x][i-1]);
            // deb(i-1);
            // deb(up[up[x][i-1]][i-1]);
            up[x][i] = up[up[x][i-1]][i-1];
        }
        // deb(1);
        for (auto to:v[x]) {
            if (to == p) continue;
            d[to] = d[x] + 1;
            self(self,to,x);
        }
        out[x] = timer;
    };

    d[1] = 1;
    dfs(dfs,1,0);

    // deb(2);

    auto ispar = [&](int x, int y) {
        return (in[x] <= in[y] && out[y] <= out[x]);
    };

    auto lca = [&](int a, int b) {
        if (ispar(a,b)) return a;
        if (ispar(b,a)) return b;
        for (int i = 20; i >= 0; i--) {
            if (up[b][i] == 0) continue;
            if (!ispar(up[b][i],a)) {
                // deb(i);
                b = up[b][i];
            }
        }
        // deb(b);
        return up[b][0];
    };
    // deb(lca(3,7));
    // deb(up[6][2]);
    // deb(lca(1,3));

    vector <int> ans(sz(S));
    for (int i = 0; i < sz(S); i++) {
        // deb(i);
        int a = S[i]+1;
        int b = T[i]+1;

        if (ispar(a,b)) {
            // deb(1);
            ans[i] = d[b]-d[a]+1;
            continue;
        }

        if (ispar(b,a)) {
            // deb(2);
            ans[i] = d[a]-d[b]+1;
            continue;
        }

        int l = lca(a,b);
        // deb(l);
        // deb(d[b]);
        // deb(d[a]);
        // deb(d[l]);
        ans[i] = d[b] + d[a] - 2*d[l] + 1;
    }

    return ans;

    

}
