#include "infection.h"
#include <bits/stdc++.h>
#include <vector>
#include <utility>

using namespace std;

int dist[5005][5005];
vector<int>adj[5005];

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
) {
    /*int N,M; cin >> N >> M;
    vector<pair<int,int>>R(N-1);
    for(int i=0; i<N-1; i++) cin >> R[i].first >> R[i].second;
    vector<long long>D(M);
    vector<int>S(M);
    vector<int>T(M);
    vector<int>I(M);
    for(int i=0; i<M; i++) {
        cin >> D[i];
        cin >> S[i];
        cin >> T[i];
        cin >> I[i];
    }*/

    int n = R.size() + 1;
    int m = I.size();

    for(int i=0; i<n-1; i++) {
        adj[R[i].first].push_back(R[i].second);
        adj[R[i].second].push_back(R[i].first);
    }

    for(int i=0; i<n; i++) {
        queue<pair<int,int>>q;
        vector<int>visited(n+1,0);
        q.push({i,0});
        while(!q.empty()) {
            pair<int,int> v = q.front(); q.pop();
            if(visited[v.first]) continue;
            visited[v.first] = 1;
            dist[i][v.first] = v.second;
            for(auto u : adj[v.first]) {
                if(!visited[u]) q.push({u, v.second+1});
            }
        }
    }

    // simulacija
    int grad[m]; // trenutni grad partygoera i
    for(int i=0; i<m; i++) grad[i] = S[i];
    vector<int>ans(m,0);
    for(int i=0; i<n; i++) { // trenutna sekunda
        // infectat svakog
        vector<int>inf(n,0);
        for(int j=0; j<m; j++) {
            if(grad[j] == 1e9) continue;
            if(I[j]) inf[grad[j]] = 1;
        }
        for(int j=0; j<m; j++) {
            if(grad[j] == 1e9) continue;
            if(inf[grad[j]]) I[j] = 1;
            if(I[j]) ans[j]++;
        }
        // pomjeriti svakog
        for(int j=0; j<m; j++) {
            int s = grad[j], t = T[j];
            if(s == t or s == 1e9) {
                grad[j] = 1e9;
                continue;
            }
            for(auto u : adj[s]) {
                if(dist[s][t] > dist[u][t]) {
                    grad[j] = u;
                    break;
                }
            }
        }
        //for(int j=0; j<m; j++) cout << grad[j] << " ";
        //cout << endl;
    }
    return ans;
}
