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

#define ll long long
const ll N=5001;
const ll INF=1e18;
vector<int>G[N];

ll dd[N][N];
ll ff[N];
map<pair<int,int>,int>infc;

vector<int>solve(vector<pair<int, int>>R,vector<long long>D,vector<int>S,vector<int>T,vector<bool>I)
{
      int n=(int)R.size()+1;
      for(int i=0;i<n;i++) ff[i]=INF;
      for(int i=0;i<n-1;i++){
            G[R[i].first].push_back(R[i].second);
            G[R[i].second].push_back(R[i].first);
      }
      for(int i=0;i<n;i++){
            for(int j=0;j<n;j++) dd[i][j]=INF;
            queue<int>q;
            dd[i][i]=0;
            q.push(i);
            while(!q.empty()){
                  int v=q.front();
                  q.pop();
                  for(int u:G[v]){
                        if(dd[i][v]+1<dd[i][u]){
                              dd[i][u]=dd[i][v]+1;
                              q.push(u);
                        }
                  }
            }
      }
      int m=(int)S.size();
      /*
      for(int i=0;i<m;i++){
            if(!I[i]) continue;
            ll day=D[i];
            ll cur=S[i];
            ll fin=T[i];
            while(1){
                  infc[{cur,day}]=1;
                  day++;
                  if(cur==fin) break;
                  ll mn=INF;
                  for(int u:G[cur]) mn=min(mn,dd[u][fin]);
                  for(int u:G[cur]){
                        if(dd[u][fin]==mn){
                              cur=u;
                              break;
                        }
                  }
            }
      }
      for(int i=0;i<m;i++){
            ll day=D[i];
            ll cur=S[i];
            ll fin=T[i];
            ll res=0;
            while(1){
                  if(infc[{cur,day}]) I[i]=1;
                  res+=I[i];
                  if(cur==fin) break;
                  day++;
                  ll mn=INF;
                  for(int u:G[cur]) mn=min(mn,dd[u][fin]);
                  for(int u:G[cur]){
                        if(dd[u][fin]==mn){
                              cur=u;
                              break;
                        }
                  }
            }
      }
      */
      vector<int>res(m);
      for(int i=0;i<m;i++){
            if(!I[i]) continue;
            res[i]=dd[S[i]][T[i]]+1;
      }
      return {res};
}
