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

#include "infection.h"

#ifdef __LOCAL__
    #include "grader_infection.cpp"
#endif // __LOCAL__

const int64_t INF = 1e18;
const int MAXN = 5003;
class Tree
{
private:
    struct Meeting
    {
        int u, v;
        int64_t d;

        Meeting(){}
        Meeting(int u, int v, int64_t d)
            :u(u), v(v), d(d){}

        bool operator< (const Meeting& other)
        {
            return d < other.d;
        }
    };

    int N, M;
    vector <int> graph[MAXN];
    int64_t endDay[MAXN];
    vector <pair <int64_t, int>> visited[MAXN];
    vector <Meeting> meetings;
    bool used[MAXN];

    bool DFS(int personIdx, int node, const int endingCity, int64_t d)
    {
        used[node] = true;
        if (node == endingCity)
        {
            visited[node].emplace_back(d, personIdx);
            endDay[personIdx] = d;
            return true;
        }

        bool ans = false;
        for (int i:graph[node])
        {
            if (used[i])
                continue;

            bool currAns = DFS(personIdx, i, endingCity, d+1);
            ans |= currAns;

            if (currAns == true)
            {
                visited[node].emplace_back(d, personIdx);
            }
        }

        return ans;
    }

    void FindMeetings()
    {
        for (int i = 0; i < N; i++)
        {
            sort(visited[i].begin(), visited[i].end());

            for (int j = 0; j < visited[i].size(); j++)
            {
                int k = j+1;
                vector <int> met = {visited[i][j].second};
                while (k < visited[i].size() && visited[i][j].first == visited[i][k].first)
                {
                    met.push_back(visited[i][k].second);
                    k++;
                }

                for (int l = 0; l < met.size(); l++)
                {
                    for (int r = l+1; r < met.size(); r++)
                    {
                        meetings.emplace_back(met[l], met[r], visited[i][j].first);
                    }
                }
                j = k-1;
            }
        }

        sort(meetings.begin(), meetings.end());
        /*for (int i = 0; i < meetings.size(); i++)
        {
            cout << meetings[i].u << " " << meetings[i].v << " " << meetings[i].d << endl;
        }*/
    }
public:
    Tree(int N, int M)
        :N(N), M(M){}

    void AddEgde(int u, int v)
    {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    void FillStayTime(int personIdx, int64_t startingDay, int startingCity, int endingCity)
    {
        memset(used, false, sizeof(used));
        DFS(personIdx, startingCity, endingCity, startingDay);
    }

    vector<int> GetAnswer(int64_t* infectedStartDay)
    {
        FindMeetings();
        for (auto [u, v, d]: meetings)
        {
            if (infectedStartDay[u] != INF || infectedStartDay[v] != INF)
            {
                infectedStartDay[u] = min(infectedStartDay[u], d);
                infectedStartDay[v] = min(infectedStartDay[v], d);
            }
        }


        vector <int> ans(M);
        for (int i = 0; i < M; i++)
        {
            if (infectedStartDay[i] == INF)
                ans[i] = 0;

            else
                ans[i] = (int)(endDay[i]-infectedStartDay[i]+1);
        }

        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
) {
   int N = R.size()+1;
   int M = D.size();
   Tree *tree = new Tree(N-1, M);

   for (int i = 0; i < N-1; i++)
   {
       tree->AddEgde(R[i].first, R[i].second);
   }

   for (int i = 0; i < M; i++)
   {
       tree->FillStayTime(i, D[i], S[i], T[i]);
   }

    int64_t infectedStartDay[MAXN];
    for (int i = 0; i < M; i++)
    {
        infectedStartDay[i] = INF;
        if (I[i] == 1)
            infectedStartDay[i] = D[i];
    }

   return tree->GetAnswer(infectedStartDay);
}

/*
9 2
0 1
1 2
2 3
3 4
4 5
3 6
6 7
6 8
3 5 7 0
4 5 7 0

*/
