#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<vector<ll>>a;
vector<ll>p;
vector<vector<ll>>p1;
vector<int>ans;
void dfs(ll cur,ll parent){
    p[cur]=parent;
    for(int i=0;i<a[cur].size();i++){
        if(a[cur][i]==parent)continue;
        dfs(a[cur][i],cur);
    }
}
void dfs1(ll cur,ll last,ll q){
    p1[cur][q]=last;
    if(cur==0)return;
    dfs1(p[cur],cur,q);
}
void upd(vector<array<ll,5>>&cur){
    vector<ll>q(a.size()+1);
    for(int i=0;i<cur.size();i++){
        if(cur[i][2]==1)q[cur[i][0]]=1;
    }
    for(int i=0;i<cur.size();i++){
        if(q[cur[i][0]]==1){
            if(cur[i][2]==0){
                cur[i][2]=1;
            }
        }
    }
}
void f(vector<array<ll,5>>&cur){
    vector<array<ll,5>>ncur;
    for(int i=0;i<cur.size();i++){
            //cout<<cur[i][0]<<' '<<cur[i][1]<<' '<<p[cur[i][0]]<<' '<<p1[cur[i][0]][cur[i][1]]<<endl;
        if(cur[i][0]==cur[i][1]){
                ans[cur[i][4]]=cur[i][3]+cur[i][2];
                continue;
        }
        if(p1[cur[i][0]][cur[i][1]]==-1)ncur.push_back({p[cur[i][0]],cur[i][1],cur[i][2],cur[i][3]+cur[i][2],cur[i][4]});
        else ncur.push_back({p1[cur[i][0]][cur[i][1]],cur[i][1],cur[i][2],cur[i][3]+cur[i][2],cur[i][4]});
    }
    swap(ncur,cur);
}
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){
    a.resize(R.size()+1);
    for(int i=0;i<R.size();i++){
        a[R[i].first].push_back(R[i].second);
        a[R[i].second].push_back(R[i].first);
    }
    int n=a.size(),m=D.size();
    p1.resize(n+1,vector<ll>(n+1,-1));
    p.resize(n);
    ans.resize(m,-1e9);
    dfs(0,0);
    for(int i=0;i<n;i++){
        dfs1(i,i,i);
    }
    vector<array<ll,5>>x;
    for(int i=0;i<m;i++){
        x.push_back({D[i],S[i],T[i],I[i],i});
    }
    sort(x.begin(),x.end());
    vector<array<ll,5>>cur;
    ll t=0;
    for(int i=0;i<x.size();i++){
        while(cur.size()&&t!=x[i][0]){
            f(cur);
            upd(cur);
            t++;
        }
        t=x[i][0];
        cur.push_back({x[i][1],x[i][2],x[i][3],0,x[i][4]});
        upd(cur);
    }
    while(cur.size()){
        f(cur);
        upd(cur);
    }
    return ans;
}