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

using namespace std;

const int NMAX = 5000;

vector<int> g[NMAX + 3];
vector<int> lvl(NMAX + 3, 0);
int t[NMAX + 3][25], inf[NMAX + 3];
int dfsin[NMAX + 3], dfsout[NMAX + 3];

int walk[NMAX + 3][2 * NMAX + 3];
int drm[NMAX + 3];

int n, m;

void solve5() {
    //lant
}

void solve12() {
    //brute
}

void solve4() {
    //dist de la s la t daca i e 1
}

bool isancestor(int u, int v) { //e u stramos de v
    return dfsin[u] <= dfsin[v] && dfsout[u] >= dfsout[v];
}

int lca(int x, int y) {
    if(lvl[x] > lvl[y])
        swap(x, y);

    if(isancestor(x, y))
        return x;

    for(int put = 24; put >= 0; put--) {
        if(!isancestor(t[x][put], y))
            x = t[x][put];
    }

    return t[x][0];
}

void rmq() {
    for(int node = 0; node < n; node++) {
        for(int put = 1; put < 25; put++) {
            t[node][put] = t[t[node][put - 1]][put - 1];
        }
    }
}

int timp = 0;

int dist(int x, int y) {
    int l = lca(x, y);
    return lvl[x] - lvl[l] + lvl[y] - lvl[l] + 1;
}

void dfs(int node) {
    dfsin[node] = ++timp;

//    cout<<"d "<<node<<" "<<lvl[node]<<"\n";

    for(int nxnode : g[node]) {
        if(lvl[nxnode] == 0) {
            lvl[nxnode] = lvl[node] + 1;
            t[nxnode][0] = node;
            dfs(nxnode);
        }
    }

    dfsout[node] = ++timp;
}

void calc() {
    lvl[0] = 1;
    dfs(0);
    rmq();
}

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();

    vector<int> ans(m, 0);

    int sol = 4;

    for(pair<int, int> pii : R) {
        g[pii.first].push_back(pii.second);
        g[pii.second].push_back(pii.first);
    }

    calc();

    if(sol == 4) {

        for(int i = 0; i < m; i++) {
            if(I[i] == 1)
                ans[i] = dist(S[i], T[i]);
        }

    } else if(sol == 2) {
        int maxx = 0;

        for(int person = 0; person < m; person++) {
            int x = S[person], y = T[person];
            int des = dist(x, y) - 1;
            drm[person] = des;
            maxx = max(maxx, des);
            int node = y, l = lca(x, y);

            while(node != l) {
                walk[person][des--] = node;
                node = t[node][0];
            }

            walk[person][des--] = l;
            node = x;
            des = 0;

            while(node != l) {
                walk[person][des++] = node;
                node = t[node][0];
            }

//            for(int i = 0; i < dist(x, y); i++) {
//                cout << walk[person][i] << " ";
//            }
//
//            cout << "\n";
        }

        int oras;

        for(int day = 0; day <= 10000; day++) {
            for(int node = 0; node < n; node++)
                inf[node] = 0;

            for(int person = 0; person < m; person++) {
                if(drm[person] < day)
                    break;

                oras = walk[person][day];

                if(I[person])
                    inf[oras] = 1;

//                cout << oras << " ";
            }

            for(int person = 0; person < m; person++) {
                if(drm[person] < day)
                    break;

                oras = walk[person][day];


                if(inf[oras]) {
//                        cout << person << " " << day << " rr ";
                    I[person] = 1;
                    ans[person]++;
                }
            }

//            cout << "\n";
        }

    }

    return ans;
}
