#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef pair<int, int> ii;
typedef vector<ii> vii;

int n, m;
vvi adj;
vi bfs(int d, int t) {
    vll dist(m, -1);
    dist[d] = 0;
    vi parent(m, -1);
    parent[d] = -1;
    queue<int> q;
    q.push(d);
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        for (auto node : adj[p]) {
            if (dist[node] == -1) {
                parent[node] = p;
                dist[node] = dist[p]+1;
                q.push(node);
            }
        }
    }
    vi ans;
    int i = t;
    while (i!=-1) {
        ans.push_back(i);
        i = parent[i];
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

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
){
    n = R.size()+1;
    m = D.size();
    adj.resize(n);
    bool firstsubtask = 1;
    vvi cities(n);
    for (int i = 0;i<n-1;++i) {
        int a = R[i].first;
        int b = R[i].second;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 0;i<m;++i) {
        if (D[i] != 0) {
            firstsubtask = 0;
        }
        cities[S[i]].push_back(i);
    }
    if (firstsubtask) {
        vvi paths;
        int days = 0;
        for (int i = 0;i<m;++i) {
            paths.push_back(bfs(S[i], T[i]));
            if (days < paths[i].size())
                days = paths[i].size();
        }
        vi ans(m, 0);
        for (int i = 0;i<days;++i) {
            for (int j = 0;j<m;++j) {
                if (i >= paths[j].size())
                    continue;
                int curcity = paths[j][i];
                if (I[j]) {
                    ans[j]++;
                    continue;
                }
                for (int man : cities[curcity]) {
                    if (I[man]) {
                        I[j] = 1;
                        ans[j]++;
                        break;
                    }
                }
            }
            for (int j = 0;j<m;++j) {
                if (i >= paths[j].size())
                    continue;
                vi city = cities[paths[j][i]];
                for (int k = 0;k<city.size();++k) {
                    if (city[k] == j) {
                        if (i+1 != paths[j].size()){
                            cities[paths[j][i]].erase(cities[paths[j][i]].begin()+k);
                            cities[paths[j][i+1]].push_back(j);
                        }
                        break;
                    }
                }
            }
        }
        return ans;
    }
    return {0};
}

