#define ll long long

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

const ll MAXN=2e5+3,INF=1e10;
ll n,par[MAXN],lvl[MAXN],in[MAXN],out[MAXN];
vector<ll> v[MAXN],tour[MAXN];
vector<pair<ll,ll>> path;

void dfsini(ll k, ll p, ll l){
    in[k]=path.size();
    out[k]=path.size();
    path.push_back({k,l});
    par[k]=p;
    lvl[k]=l;
    for(auto ch : v[k]){
        if(ch==p) continue;
        dfsini(ch,k,l+1);
        out[k]=path.size();
        path.push_back({k,l});
    }
}

ll tree[MAXN*8];
void build(ll k, ll l, ll r){
    if(l==r){
        tree[k]=path[l].second;
        return;
    }

    ll mid=(l+r)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);

    tree[k]=min(tree[k*2],tree[k*2+1]);
}
ll ql,qr,qans;
void query(ll k, ll l, ll r){
    if(r<ql || l>qr) return;

    if(ql<=l && r<=qr){
        qans=min(qans,tree[k]);
        return;
    }

    ll mid=(l+r)/2;
    query(k*2,l,mid);
    query(k*2+1,mid+1,r);
}

vector<int> solve(
    vector<pair<int, int>> R,
    vector<long long> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I
) {
    bool infected=0;
    for(auto f : I) if(f){infected=1; break;}
    if(!infected){
        vector<int> ans(S.size(),0);
        return ans;
    }

    for(auto edge : R){
        v[edge.first].push_back(edge.second);
        v[edge.second].push_back(edge.first);
    }

    dfsini(0,-1, 1);

    build(1,0,path.size()-1);

    ll lcal,x,y;
    ll m=D.size();
    vector<int> ans(m,0);
    for(ll i=0;i<D.size();i++){
        x=S[i]; y=T[i];
        ql=min(in[x],in[y]);
        qr=max(out[x],out[y]);
        qans=INF;
        query(1,0,path.size()-1);
        lcal=qans;

        while(1){
            tour[i].push_back(x);
            if(lvl[x]==lcal) break;
            x=par[x];
        }
        stack<ll> st;
        while(1){
            if(lvl[y]==lcal) break;
            st.push(y);
            y=par[y];
        }
        while(!st.empty()){
            tour[i].push_back(st.top());
            st.pop();
        }
    }

    bool it[MAXN];
    for(ll td=0;td<n+2;td++){
        for(ll j=0;j<n;j++) it[j]=0;
        for(ll j=0;j<m;j++){
            if(td>=tour[j].size()) continue;
            if(I[j]) it[tour[j][td]]=1;
        }

        for(ll j=0;j<m;j++){
            if(td>=tour[j].size()) continue;
            if(ans[j]>0) continue;
            if(it[tour[j][td]]==1 && I[j]==0){
                I[j]=1;
                ans[j]=tour[j].size()-td;
            }
        }
    }

    return ans;
}
