#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N, M;
ll START[5000], END[5000];
vector <int> VG[5000];
map <pair <ll, int>, vector <int>> MAP;
vector <int> O;
bool DFS(int node, int target, int id, ll t, int parent = -1)
{
  bool ret = 0;
  if(node == target) {END[id] = t; ret = 1;}
  else for(int x : VG[node]) if((x ^ parent) && DFS(x, target, id, t + 1, node)) {ret = 1; break;}
  if(ret) MAP[make_pair(t, node)].push_back(id);
  return ret;
}
vector <int> solve(vector <pair<int, int>> R, vector <ll> D, vector <int> S, vector <int> T, vector <bool> I)
{
  N = R.size() + 1;
  for(auto p : R)
  {
    VG[p.first].push_back(p.second);
    VG[p.second].push_back(p.first);
  }
  M = D.size();
  O = vector <int>(M, 0);
  for(int i = 0; i < M; i++) START[i] = -1;
  for(int i = 0; i < M; i++) DFS(S[i], T[i], i, D[i]);
  for(auto p : MAP)
  {
//    cout << p.first.first << ' ' << p.first.second << ":\n";
//    for(int x : p.second) cout << x << '\n';
    bool flag = 0;
    for(int x : p.second) flag |= I[x];
//    cout << flag << '\n';
    if(!flag) continue;
    for(int x : p.second)
    {
      I[x] = 1;
      if(START[x] < 0) START[x] = p.first.first;
    }
  }
  for(int i = 0; i < M; i++) if(START[i] != -1) O[i] = END[i] - START[i] + 1;
  return O;
}