#include<bits/stdc++.h>
#define endl "\n"
#include "infection.h"
using namespace std;
struct node{
    vector<int> people;
    bool infected;
};
struct person{
    int st,en,day,iday;
    vector<int> path;
    bool infected;
};
int n,m;
vector<int> g[5010];
person a[5010];
node b[5010];

int intime[5010];
int outime[5010];
int Ti;
int p[5010][14];
void dfs(int u,int par){
    intime[u] = Ti++;
    for(auto v: g[u]){
        if(v==par) continue;
        p[v][0] = u;
        dfs(v,u);
    }
    outime[u] = Ti++;
}
void pre(){
    for(int i=1;i<14;i++){
        for(int u=0;u<n;u++){
            p[u][i] = p[p[u][i-1]][i-1];
        }
    }
}
bool isParent(int u,int v){
    return (intime[u]<=intime[v] && outime[v]<=outime[u]);
}
int LCA(int u,int v){
    if(intime[u]>intime[v]) swap(u,v);
    if(isParent(u,v)) return u;
    for(int i=13;i>=0;i--){
        if(!isParent(p[v][i],u)) v = p[v][i];
    }
    return p[v][0];
}
vector<int> getPath(int u,int v){
    vector<int> rez;
    if(intime[u]>intime[v]) swap(u,v);
    int lca = LCA(u,v);
    if(lca==u){
        while(isParent(u,v)){
            rez.push_back(v);
            v = p[v][0];
        }
        reverse(rez.begin(),rez.end());
        return rez;
    }
    while(isParent(lca,u)){
        rez.push_back(v);
        v = p[v][0];
    }
    int left = rez.size();
    while(isParent(u,v)){
        rez.push_back(v);
        v = p[v][0];
    }
    reverse(rez.begin()+left+1,rez.end());
    return rez;
}
vector<int> solve(vector<pair<int, int>> R,vector<long long> D,vector<int> S,vector<int> T,vector<bool> I){
    n = R.size()+1;
    m = D.size();
    for(auto p: R){
        g[p.first+1].push_back(p.second+1);
        g[p.second+1].push_back(p.first+1);
    }
    dfs(0,1);
    outime[0] = Ti;
    pre();
    for(int i=0;i<m;i++){
        a[i] = {S[i]+1,T[i]+1,D[i],(I[i] ? D[i] : -1),getPath(S[i]+1,T[i]+1),I[i]};
    }
    int t=0;
    for(int t=0;t<5000;t++){
        for(int i=0;i<m;i++){
            if(t<a[i].day || t-a[i].path.size()>=a[i].day) continue;
            int idx = t-a[i].day;
            b[a[i].path[idx]].people.push_back(i);
            if(a[i].infected) b[a[i].path[idx]].infected = true;
        }
        for(int i=1;i<=n;i++){
            if(b[i].infected){
                for(auto idx: b[i].people){
                    a[i].infected = true;
                    a[i].iday = t;
                }
            }
            b[i].infected = false;
            b[i].people.clear();
        }
    }
    vector<int> ans(m);
    for(int i=0;i<m;i++){
        ans[i] = (a[i].infected ? 0 : a[i].day+a[i].path.size()-a[i].iday);
    }
    return ans;
}/*
int main(){
    int N,M;
    cin>>N>>M;
    vector<pair<int,int> > r(n-1);
    vector<long long> d(m);
    vector<int> s(m);
    vector<int> t(m);
    vector<bool> ii(m);
    for(int i=0;i<n-1;i++){
        cin>>r[i].first>>r[i].second;
    }
    for(int i=0;i<m;i++){
            int x;
        cin>>d[i]>>s[i]>>t[i]>>x;
    ii[i] = x;
    }
    vector<int> ans = solve(r,d,s,t,ii);
    for(auto x: ans){
        cout<<x<<" ";
    }
}
*/
