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

using namespace std;

typedef long long ll;

const int maxn=150005;
const int inf=1e9;
int n,m;
ll d1[maxn];
vector<int>v[maxn];
unordered_set<ll>mom[maxn];
int par[maxn];
int ans[maxn];

/*bool cmp(int a,int b)
{
    return d1[a]<d1[b];
}*/

int currans;
void dfs_prec(int node,int parent,int start,int finish,ll depth1)
{
    par[node]=parent;

    if(node==finish)
    {
        vector<int>path;
        int curr=node;
        while(curr!=par[start])
        {
            path.push_back(curr);
            curr=par[curr];
        }

        int sz=path.size();
        for(int i=0;i<sz;i++)
        {
            mom[path[i]].insert((ll)(depth1+sz-i-1));
        }

        currans=sz;

        return;
    }

    for(int i : v[node])
    {
        if(i==parent)
            continue;
        dfs_prec(i,node,start,finish,depth1);
    }
}

void dfs(int node,int parent,int start,int finish,ll depth1)
{
    par[node]=parent;

    if(node==finish)
    {
        vector<int>path;
        int curr=node;
        while(curr!=par[start])
        {
            path.push_back(curr);
            curr=par[curr];
        }

        /*cout<<"path ";
        for(int i : path)
            cout<<i<<' ';
        cout<<endl;*/

        int sz=path.size();
        ll currmom;
        for(int i=sz-1;i>=0;i--)
        {
            currmom=depth1+sz-i-1;
            //cout<<path[i]<<' '<<currmom<<endl;
            if(mom[path[i]].find(currmom)!=mom[path[i]].end())
            {
                //cout<<"hello"<<endl;
                currans=i+1;
                for(int j=i-1;j>=0;j--)
                {
                    mom[path[j]].insert((ll)(depth1+sz-j-1));
                }
                return;
            }
        }

        return;
    }

    for(int i : v[node])
    {
        if(i==parent)
            continue;
        dfs(i,node,start,finish,depth1);
    }
}

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)
{
    n=R.size()+1;
    m=D.size();

    for(pair<int,int> i : R)
    {
        v[i.first].push_back(i.second);
        v[i.second].push_back(i.first);
    }

    for(int i=0;i<m;i++)
    {
        if(I[i]==true)
        {
            dfs_prec(S[i],-1,S[i],T[i],D[i]);
            ans[i]=currans;
        }
        else
        {
            currans=0;
            dfs(S[i],-1,S[i],T[i],D[i]);
            ans[i]=currans;
        }
    }

    vector<int>ret;
    for(int i=0;i<m;i++)
        ret.push_back(ans[i]);

    return ret;
}
