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

#include "infection.h"

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

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

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

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

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

    bool DFS(int64_t personIdx, int64_t node, const int64_t 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 (int64_t 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 (int64_t i = 0; i < N; i++)
        {
            sort(visited[i].begin(), visited[i].end());

            for (int64_t j = 0; j < visited[i].size(); j++)
            {
                int64_t k = j+1;
                vector <int64_t> 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 (int64_t l = 0; l < met.size(); l++)
                {
                    for (int64_t 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 (int64_t i = 0; i < meetings.size(); i++)
        {
            cout << meetings[i].u << " " << meetings[i].v << " " << meetings[i].d << endl;
        }*/
    }
public:
    Tree(int64_t N, int64_t M)
        :N(N), M(M){}

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

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

    vector<int> GetAnswer(int64_t* infectedStartDay)
    {
        FindMeetings();
        for (int i = 0; i < meetings.size(); i++)
        {
            int64_t currDay = meetings[i].d;
            vector <int64_t> met;

            int j;
            for (j = i; j < meetings.size(); j++)
            {
                auto [u,v,d] = meetings[j];

                if (currDay != d)
                {
                    break;
                }

                met.push_back(u);
                met.push_back(v);
            }

            i = j-1;
            bool hasInfected = false;
            for (int x:met)
            {
                //cout << x << " ";
                if (infectedStartDay[x] <= currDay)
                    hasInfected = true;
            }
            //cout << endl;


            if (hasInfected == false)
                continue;

            for (int x:met)
            {
                infectedStartDay[x] = min(infectedStartDay[x], currDay);
            }
        }

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

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

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

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

   return tree->GetAnswer(infectedStartDay);
}

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


3 3
0 1
1 2
0 0 2 0
0 2 0 0
1 1 1 1
*/

