#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

ll n, m, titi;
vector<ll> dep, ti, to;
vector<vector<ll>> up, g;
void dfs(ll v, ll par) {
    ti[v] = titi++;
    up[0][v] = par;
    for (ll i = 1; i < 20; i++) {
        up[i][v] = up[i - 1][up[i - 1][v]];
    }
    for (auto &u : g[v]) {
        if (u == par) continue;
        dep[u] = dep[v] + 1;
        dfs(u, v);
    }
    to[v] = titi++;
}
bool is_p(ll v, ll u) {
    return (ti[v] <= ti[u] && to[v] >= to[u]);
}
ll lca(ll v, ll u) {
    if (is_p(v, u)) return v;
    if (is_p(u, v)) return u;
    for (ll i = 19; i >= 0; i--) {
        if (!is_p(up[i][v], u)) {
            v = up[i][v];
        }
    }
    return up[0][v];
}
ll dis(ll v, ll u) {
    return (dep[v] + dep[u] - 2 * dep[lca(v, u)] + 1);
}

vector<int> solve(vector<pii> r, vector<ll> tim, vector<int> s, vector<int> t, vector<bool> is) {
    n = r.size() + 1;
    m = is.size();

    titi = 0;
    ti.assign(n, 0);
    to.assign(n, 0);
    g.assign(n, {});
    for (auto &[v, u] : r) {
        g[v].push_back(u);
        g[u].push_back(v);
    }
    dep.assign(n, 0);
    up.assign(20, vector<ll> (n));
    dfs(0, 0);

    vector<int> res(m);
    for (int i = 0; i < m; i++) {
        res[i] = (is[i] ? dis(s[i], t[i]) : 0);
    }
    return res;
}