#include "infection.h"
#include <bits/stdc++.h>
// #include "grader.cpp"

using namespace std;

using ll = long long;

#define ff  first
#define ss  second
#define pii pair<int, int>

#define sz(a)  (int)(a).size()
#define all(a) (a).begin(), (a).end()

const int N = 150000 + 1;

int n, m, Tm, x, y, pr[N], in[N], out[N];

vector<int> E[N], p[N], v, ans;

void dfs(int x) {
    in[x] = Tm++;

    for (auto i : E[x]) {
        if (i == pr[x]) continue;
        pr[i] = x; dfs(i);
    }

    out[x] = Tm++;
}

vector<int> solve(vector<pair<int, int>> R, vector<ll> D, vector<int> S, vector<int> T, vector<bool> I) {
    n = sz(R) + 1; m = sz(D);

    for (auto [x, y] : R) {
        E[x].push_back(y);
    }
    R.clear();

    dfs(0);

    for (int i = 0; i < m; i++) {
        x = S[i]; y = T[i];
        while (!(in[x] <= in[y] && out[y] <= out[x])) {
            p[i].push_back(x); x = pr[x];
        }
        p[i].push_back(x);

        while (x != y) {
            v.push_back(y); y = pr[y];
        }
        reverse(all(v));

        p[i].insert(p[i].end(), all(v)); v.clear();
    }

    ans.assign(m, 0);
    for (int i = 0; i < m; i++) {
        ans[i] = (I[i] ? sz(p[i]) : 0);
    }

    return ans;
}