#define ll long long
#define se second
#define fi first
using namespace std;
#include<utility>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<unordered_map>

const char nl = '\n';
const ll inf = 1e18;

vector <vector <int> > g;

    struct st{
        int x, i, u;
    };

    bool cmp(st a, st b) {
        if (a.x != b.x) {
            return a.x < b.x;
        } else {
            return a.u < b.u;
        }
    }

    unordered_map <ll, int> F(set <ll> &a) {
        int i = 0;
        unordered_map <ll, int> nw;
        for (auto it : a) {
            nw[it] = i;
            i++;
        }
        return nw;
    }

    int dfs(vector <int> &a, int v, int p, int c) {
        a.push_back(v);
        if (v == c) {
            return 1;
        }
        for (auto u : g[v]) {
            if (u == p) {
                continue;
            }
            if (dfs(a, u, v, c)) {
                return 1;
            }
        }
        a.pop_back();
        return 0;
    }

    std::vector<int> solve(
    std::vector<std::pair<int, int>> r,
    std::vector<ll> d,
    std::vector<int> s,
    std::vector<int> t,
    std::vector<bool> I
    ) {
        int n = r.size() + 1;
        int m = d.size();
        bool f = 1;
        g.resize(n);
        for (int i = 0; i < n - 1; i++) {
            if (!(r[i].fi == i && r[i].se == i + 1)) {
                f = 1;
            }
            g[r[i].fi].push_back(r[i].se);
            g[r[i].se].push_back(r[i].fi);
        }

        vector <ll> ans(m, -1);
        vector <vector <int> > p(m);
        set <ll> cord;
        for (int i = 0; i < m; i++) {
            int x = dfs(p[i], s[i], -1, t[i]);
            for (int j = 0; j < p[i].size(); j++) {
                cord.insert(j + d[i]);
            }
        }

        unordered_map <ll, int> nw = F(cord);

        vector <vector <pair <int, int> > > pos(nw.size());
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < p[i].size(); j++) {
                pos[nw[d[i] + j]].push_back({p[i][j], i});
            }
        }

        vector <int> is(n);

        for (auto &it : cord) {
            //cout << it.fi << ": " << nl;
            for (auto &j : pos[nw[it]]) {
                //cout << j.fi << ' ' << j.se << nl;
                if (I[j.se] || ans[j.se] != -1) {
                    is[j.fi] = 1;
                }
            }
            for (auto &j : pos[nw[it]]) {
                if (is[j.fi]) {
                    if (ans[j.se] == -1) {
                        ans[j.se] = it;
                    }
                }
            }

            for (auto &j : pos[nw[it]]) {
                is[j.fi] = 0;
            }

        }

        vector <int> ans1(m, -1);

        for (int i = 0; i < m; i++) {
            if (ans[i] == -1) {
                ans[i] = 0;
            } else {
                ans[i] = p[i].size() + d[i] - ans[i];
            }
            ans1[i] = ans[i];
        }
        return ans1;
    };