#include <algorithm>
#include <climits>
#include <vector>
#include "iostream"
std::vector<std::vector<int>> g(150000);
std::vector<std::vector<int>> lca(150000, std::vector<int>(20, 0));
std::vector<int> pre(150000, -1), post(150000), h(150000, 0);
int count = 0;
void dfs(int v) {
  pre[v] = count++;
  for(int w : g[v]) {
    if(pre[w] == -1) {
      lca[w][0] = v;
      h[w] = h[v]+1;
      dfs(w);
    }
  }
  post[v] = count++;
}
bool isanc(int p, int c) {
  return pre[p] <= pre[c] && post[c] <= post[p];
}
int flca(int a, int b) {
  if(isanc(b, a)) std::swap(a, b);
  if(isanc(a, b)) return a;
  for(int k = 19; k >= 0; --k) {
    if(isanc(lca[a][k], b)) continue;
    a = lca[a][k];
  }
  return lca[a][0];
}

void path(int a, int b, std::vector<int>& p) {
  if(isanc(b, a)) std::swap(a, b);
  if(isanc(a, b)) {
    std::vector<int> p2;
    while(b != a) {
      p2.push_back(b);
      b = lca[b][0];
    }
    p.push_back(a);
    for(int i = p2.size()-1; i >= 0; --i) p.push_back(p2[i]);
    return;
  }
  p.push_back(a);
  path(lca[a][0], b, p);
}

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
) {
  const long long INF = LLONG_MAX;
  for(auto e : R) {
    g[e.first].push_back(e.second);
    g[e.second].push_back(e.first);
  }
  std::vector<int> out;
  dfs(0);
  for(int k = 1; k < 20; ++k) for(int i = 0; i < 150000; ++i) lca[i][k] = lca[lca[i][k-1]][k-1];
  std::vector<long long> starti(I.size(), INF), end(I.size(), -1000000000LL);

  for(int i = 0; i < I.size(); ++i) if(I[i]) starti[i] = D[i];
  std::vector<int> isin(150001, 0);
  if(I.size() > 5000) {
    for(int i = 0; i < I.size(); ++i) {
      if(!I[i]) {
        out.push_back(0);
        continue;
      }
      int lc = flca(S[i], T[i]);
      out.push_back(1+h[S[i]]+h[T[i]]-h[lc]-h[lc]);

    }
    return out;
  } else {
    std::vector<std::pair<long long, std::pair<std::pair<int, int>, int>>> sl;
    for(int i = 0; i < I.size(); ++i) {
      std::vector<int> p;
      path(S[i], T[i], p);
      for(int t = 0; t < p.size(); ++t) {
        sl.push_back({D[i]+t, {{p[t], t == 0 ? 150000 : p[t-1]}, i}});
      }
      sl.push_back({D[i]+(long long) p.size(), {{150000, p.back()}, i}});
    }
    std::sort(sl.begin(), sl.end());
    sl.push_back({0LL, {{0, 0}, 0}});
    long long lt = -1;
    std::vector<std::pair<int, int>> trans;
    for(int i = 0; i < sl.size(); ++i) {
      auto [t, _a] = sl[i];
      auto [_d, p] = _a;
      auto [a, b] = _d;
      if(t != lt) {
        for(auto [place, person] : trans) {
          if(place == 150000) {
            end[person] = lt;
            continue;
          }
          if(isin[place] > 0) {
            if(!I[person]) {
              I[person] = true;
              ++isin[place];
            }
            starti[person] = std::min(starti[person], lt);
          }
        }
        trans.clear();
        lt = t;
      }
      if(I[p]) {
        ++isin[a];
        --isin[b];
      }
        trans.push_back({a, p});
    }
    for(int i = 0; i < I.size(); ++i) {
      out.push_back(std::max(0LL, end[i]-starti[i]));
    }
  }
  return out;
}
