#include "infection.h"
#include <vector>
#include <bits/stdc++.h>
#include <utility>
#define pb push_back
using namespace std;
const int maxn = 5e3 +10;
int dep[maxn];
vector < int > g[maxn];
unordered_map < long long, vector < int > > mp[maxn]; /// den, hora za vsqka staq
unordered_map < long long, int > dayused;
int n, m, p[maxn];
void dfs(int beg, int from, int h)
{
    dep[beg] = h;
    p[beg] = from;
    for (auto nb: g[beg])
    {
        if(nb == from)continue;
        dfs(nb, beg, h +1);
    }
}

vector < pair < long long, int > > av;
int jump[maxn][23];

int moveup(int ver, int x)
{
    for (int i = 0; i <= 20; ++ i)
        if(x & (1 << i))ver = jump[ver][i];
    return ver;
}
int lca(int u, int v)
{
    int depu = dep[u], depv = dep[v];
    int delta = abs(depu - depv);
    if(depu > depv)
        u = moveup(u, delta);
    else v = moveup(v, delta);
    if(u == v)return u;
    for (int i = 20; i >= 0; -- i)
    {
        int du = moveup(u, (1 << i));
        int dv = moveup(v, (1 << i));
        if(dv == du)continue;
        u = du;
        v = dv;
    }
    return p[u];
}
vector < int > path[maxn];
long long inf[maxn], started[maxn];
int pos[maxn];
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 = (int)R.size()+1;
    m = (int)D.size();
    for (auto &[from, to]: R)
    {
        g[from].pb(to);
        g[to].pb(from);
    }
    dfs(0, 0, 0);
    for (int i = 0; i < n; ++ i)
        jump[i][0] = p[i];
    for (int j = 1; j <= 20; ++ j)
    {
        for (int i = 0; i < n; ++ i)
            jump[i][j] = jump[jump[i][j-1]][j-1];
    }

    vector < int > ans;

    for (int i = 0 ; i < m; ++ i)
    {
        int s = S[i];
        int t = T[i];
        int meet = lca(s, t);
        int dist = dep[s] + dep[t] - 2*dep[meet] + 1;

        vector < int > up, down;
        int curr = s;
        while(curr != meet)
        {
            up.pb(curr);
            curr = p[curr];
        }
        up.pb(meet);
        curr = t;
        while(curr != meet)
        {
            down.pb(curr);
            curr = p[curr];
        }
        reverse(down.begin(), down.end());
        for (auto x: up)
            path[i].pb(x);
        for (auto x: down)
            path[i].pb(x);
        inf[i] = I[i];
        if(I[i])started[i] = D[i];
        else started[i] = 1e17;
        pos[i] = 0;

        long long den = D[i];

        //for (int i = 0; i < path.size())
        for (auto x: path[i])
        {
            dayused[den] ++;
           // cout <<
            mp[x][den].pb(i);
          // cout << x << endl;
          //  mp[curr][den] = i;


            if(mp[x][den].size() == 1)
                av.pb(make_pair(den, x));
            den ++;
        }
    }
    sort(av.begin(), av.end());
    for (auto &[day, room]: av)
    {
        if(dayused[day] == 1)continue;
       // cout << day << " " << room << endl;
        int s = 0;
        for (auto x: mp[room][day])
        {
            s += inf[x];
        }
        if(s)
        {
            for (auto x: mp[room][day])
            {
                started[x] = min(started[x], (long long)day);
                inf[x] = 1;
            }
        }
    }

    for (int i =0 ; i < m; ++ i)
    {
        if(started[i] == 1e17)ans.pb(0);
        else ans.pb(D[i] + path[i].size()  - started[i]);
    }
    return ans;
}
