#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
using namespace std;
int N, M;
vector <int> VG[150001];
int DP[150001];
int UP[20][150001];
void DFS(int node, int parent = -1)
{
  UP[0][node] = parent;
  for(int i = 1; (1 << i) < DP[node]; i++) UP[i][node] = UP[i - 1][UP[i - 1][node]];
  for(int x : VG[node])
  {
    if(x == parent) continue;
    DP[x] = DP[node] + 1;
    DFS(x, node);
  }
  return;
}
int LCA(int u, int v)
{
  if(DP[u] > DP[v]) swap(u, v);
  for(int i = 17; i >= 0; i--) if((UP[i][v] >= 0) && (DP[UP[i][v]] >= DP[u])) v = UP[i][v];
  if(u == v) return u;
  for(int i = 17; i >= 0; i--)
  {
    if((UP[i][u] >= 0) && (UP[i][v] >= 0) && (UP[i][u] != UP[i][v])) {u = UP[i][u]; v = UP[i][v];}
  }
  return UP[0][u];
}
vector <int> solve(vector <pair<int, int>> R, vector <ll> D, vector <int> S, vector <int> T, vector <bool> I)
{
  memset(UP, -1, sizeof(UP));
  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();
  DP[0] = 1;
  DFS(0);
  vector <int> O(M);
  for(int i = 0; i < N; i++) cout << DP[i] << ' ';
  cout << '\n';
  for(int i = 0; i < M; i++)
  {
    O[i] = 0;
    if(!I[i]) continue;
    O[i] = DP[S[i]] + DP[T[i]] - (DP[LCA(S[i], T[i])] << 1) + 1;
  }
  return O;
}