#include "infection.h"
using namespace std;

#define MAXN 150000

vector<int> adj[MAXN];
int n;
int depth[MAXN],parent[MAXN];

void dfs(int u,int p,int d){
  depth[u]=d;
  parent[u]=p;
  for(int v:adj[u]){
    if(v!=p){
      dfs(v,u,d+1);
    }
  }
}

int getLen(int st,int dr){
  int len=0;

  if(depth[dr]<depth[st]){
    swap(st,dr);
  }

  while(depth[st]<depth[dr]){
    len++;
    dr=parent[dr];
  }

  while(st!=dr){
    len+=2;
    st=parent[st];
    dr=parent[dr];
  }

  return len-1;
}

vector<int> solve(vector<pair<int, int>> R,vector<long long> D,vector<int> S,vector<int> T,vector<bool> I){
  n=D.size();

  for(auto p:R){
    adj[p.first].push_back(p.second);
    adj[p.second].push_back(p.first);
  }

  dfs(0,-1,0);

  bool inf=false;
  for(int x:I){
    if(x){
      inf=true;
      break;
    }
  }

  vector<int> ans;
  for(int i=0;i<n;i++){
    if(inf){
      ans.push_back(getLen(S[i],T[i]));
    }else{
      ans.push_back(0);
    }
  }

  return ans;
}
