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

#define int long long
const int INF = 1e18;

void myassert(bool bl)
{
    if(!bl)
    {
        //while(1);
        assert(0);
    }
}

struct DS
{
    vector<int> who;
    set<pair<int,pair<int,int>>> s;

    //map<pair<int,int>,bool> mp;
    set<pair<int,int>> mp;

    void init(vector<int> cv)
    {
        who = cv;
        mp.clear();
    }
    void update(int le, int ri, int state)
    {
        myassert(le <= ri);
        myassert(0 <= le && ri < who.size());

        //s.insert({state, {le, ri}});

        for(int u=le;u<=ri;u++)
            mp.insert({u, state + u});
    }
    void update_reverse(int le, int ri, int day)
    {
        myassert(le <= ri);
        myassert(0 <= le && ri < who.size());

        //goes from ri to le, starting from this day
        for(int u=ri;u>=le;u--)
            mp.insert({u, day + (ri - u)});
    }
    int query_for_reverse(int le, int ri, int state)
    {
        myassert(le <= ri);
        myassert(0 <= le && ri < who.size());

        int mnm = INF;
        for(int u=le;u<=ri;u++)
            if(mp.find({u, state + u}) != mp.end())
                mnm = min(mnm, u);
        //cerr<<who[0]<<": "<<le<<" "<<ri<<" "<<state<<": "<<mnm<<" qry rev\n";
        return mnm;
    }
    int query(int le, int ri, int state)//returns after how many seconds it gets infected
    {
        myassert(le <= ri);
        myassert(0 <= le && ri < who.size());

        /*int mnm = INF;
        for(auto it:s)
        {
            if(it.first != state)
                continue;
            int his_le = it.second.first, his_ri = it.second.second;
            if(his_ri < le)
                continue;
            if(ri < his_le)
                continue;

            if(his_le <= le)
                mnm = min(mnm, le);
            mnm = min(mnm, his_le);
        }
        return min(mnm, query_for_reverse(le, ri, state));*/

        int x = query_for_reverse(le, ri, state);
        if(x != INF)
            myassert(le <= x && x <= ri);
        return x;
    }
};

int n;
vector<int> con[150005];

DS up[150005], down[150005];
int poz_up[150005], poz_down[150005];

int parent[150005], siz[150005], depth[150005], tin[150005], tout[150005], timer, head[150005];
void dfs(int nod)
{
    siz[nod] = 1;
    for(int adj:con[nod])
    {
        if(adj == parent[nod])
            continue;
        parent[adj] = nod;
        depth[adj] = depth[nod] + 1;
        dfs(adj);
        siz[nod] += siz[adj];
    }
}

void decompose(int nod, int chead)
{
    tin[nod] = ++timer;
    head[nod] = chead;
    int heavy = -1;
    for(int adj:con[nod])
    {
        if(adj == parent[nod])
            continue;
        if(heavy == -1 || siz[adj] > siz[heavy])
            heavy = adj;
    }

    //heavy = -1;

    if(heavy != -1)
        decompose(heavy, chead);
    for(int adj:con[nod])
        if(adj != parent[nod] && adj != heavy)
            decompose(adj, adj);

    if(heavy == -1)
    {
        //init DSs for chain-----------------------------------------------------------------------------


        vector<int> aux;
        int cur = nod;
        while(1)
        {
            aux.push_back(cur);
            if(cur == head[nod])
                break;
            cur = parent[cur];
        }


        for(int i=0;i<aux.size();i++)
            poz_up[aux[i]] = i;
        up[head[nod]].init(aux);

        reverse(aux.begin(), aux.end());
        for(int i=0;i<aux.size();i++)
            poz_down[aux[i]] = i;
        down[head[nod]].init(aux);

        //for(int x:aux) cerr<<x<<" ";cerr<<"chain\n";

    }
    tout[nod] = timer;
}

int anc[150005][19];
bool isanc(int x, int y)
{
    return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}
int lca(int x, int y)
{
    if(isanc(x,y))
        return x;
    if(isanc(y,x))
        return y;
    for(int p=18;p>=0;p--)
        if(!isanc(anc[x][p],y))
            x = anc[x][p];
    return anc[x][0];
}

void infect(int s, int t, int day)
{
    //cerr<<s<<" "<<t<<"  "<<day<<" infect\n";
    int lc = lca(s, t);

    int cur = s;
    while(head[cur] != head[lc])
    {
        up[head[cur]].update(poz_up[cur], poz_up[head[cur]], -poz_up[cur] + day + (depth[s] - depth[cur]));

        down[head[cur]].update_reverse(poz_down[head[cur]], poz_down[cur], day + (depth[s] - depth[cur]));

        cur = parent[head[cur]];
    }
    up[head[cur]].update(poz_up[cur], poz_up[lc], -poz_up[cur] + day + (depth[s] - depth[cur]));

    down[head[cur]].update_reverse(poz_down[lc], poz_down[cur], day + (depth[s] - depth[cur]));

    cur = t;
    while(head[cur] != head[lc])
    {
        down[head[cur]].update(poz_down[head[cur]], poz_down[cur], -poz_down[cur] + day + (depth[s] - depth[lc]) + (depth[cur] - depth[lc]));

        up[head[cur]].update_reverse(poz_up[cur], poz_up[head[cur]], day + (depth[s] - depth[lc]) + (depth[head[cur]] - depth[lc]));

        cur = parent[head[cur]];
    }
    down[head[cur]].update(poz_down[lc], poz_down[cur], -poz_down[cur] + day + (depth[s] - depth[lc]) + (depth[cur] - depth[lc]));

    up[head[cur]].update_reverse(poz_up[cur], poz_up[lc], day + (depth[s] - depth[lc]));
}

std::vector<int32_t> solve(
    std::vector<std::pair<int32_t, int32_t>> R,
    std::vector<long long> D,
    std::vector<int32_t> S,
    std::vector<int32_t> T,
    std::vector<bool> I)
{
    int q = I.size();
    n = R.size() + 1;
    for(int i=0;i<n-1;i++)
    {
        con[R[i].first].push_back(R[i].second);
        con[R[i].second].push_back(R[i].first);
    }

    dfs(0);
    decompose(0,0);

    for(int i=0;i<n;i++)
        anc[i][0] = parent[i];
    anc[0][0] = 0;
    for(int p=1;p<19;p++)
        for(int i=0;i<n;i++)
            anc[i][p] = anc[anc[i][p-1]][p-1];

    vector<pair<pair<int,int>,int>> ord;
    for(int i=0;i<q;i++)
        ord.push_back({{D[i], !I[i]}, i});
    sort(ord.begin(), ord.end());

    vector<int32_t> rez(q, -1);

    for(auto [_,i]:ord)
    {
        if(I[i])
        {
            int lc = lca(S[i], T[i]);

            rez[i] = depth[S[i]] + depth[T[i]] - 2 * depth[lc] + 1;
            infect(S[i], T[i], D[i]);
        }
        else
        {
            int lc = lca(S[i], T[i]);
            rez[i] = 0;

            int unde = -1;

            int cur = S[i];
            while(head[cur] != head[lc])
            {
                int x = up[head[cur]].query(poz_up[cur], (int)up[head[cur]].who.size() - 1, -poz_up[cur] + D[i] + (depth[S[i]] - depth[cur]));
                if(x != INF)
                {
                    unde = up[head[cur]].who[x];
                    break;
                }
                cur = parent[head[cur]];
            }
            if(unde == -1)
            {
                int x = up[head[cur]].query(poz_up[cur], poz_up[lc], -poz_up[cur] + D[i] + (depth[S[i]] - depth[cur]));
                if(x != INF)
                {
                    unde = up[head[cur]].who[x];
                }
            }

            if(unde != -1)
            {
                infect(unde, T[i], D[i] + (depth[S[i]] - depth[unde]));
                rez[i] = (depth[unde] - depth[lc]) + 1 + (depth[T[i]] - depth[lc]);
                //cerr<<i<<" "<<rez[i]<<" rez1\n";
                continue;
            }

            myassert(unde == -1);

            cur = T[i];
            //vector<pair<pair<int,int>,int>> idk;
            vector<int> idk;
            while(head[cur] != head[lc])
            {
                int x = down[head[cur]].query(0, poz_down[cur], -poz_down[cur] + D[i] + (depth[S[i]] - depth[lc]) + (depth[cur] - depth[lc]));
                if(x != INF)
                    idk.push_back(down[head[cur]].who[x]);
                cur = parent[head[cur]];
            }

            int x = down[head[cur]].query(poz_down[lc], poz_down[cur], -poz_down[cur] + D[i] + (depth[S[i]] - depth[lc]) + (depth[cur] - depth[lc]));
            if(x != INF)
                idk.push_back(down[head[cur]].who[x]);

            reverse(idk.begin(), idk.end());

            for(int nod:idk)
            {
                unde = nod;
                break;
            }

            if(unde != -1)
            {
                infect(unde, T[i], D[i] + (depth[S[i]] - depth[lc]) + (depth[unde] - depth[lc]));
                rez[i] = depth[T[i]] - depth[unde] + 1;
                //cerr<<i<<" "<<rez[i]<<" rez2\n";
                continue;
            }

            rez[i] = 0;
        }
    }

    return rez;
}

/*

9 5
0 1
1 2
2 3
3 4
4 5
3 6
6 7
6 8
1 0 5 1
3 5 7 0
4 5 7 0
8 7 8 0
10 0 1 0

correct:
6
0
4
3
0

*/