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

const int MAXN = 5e3;
const int LOG = 20;

int n , up[LOG + 1][MAXN + 1] , par[MAXN + 1] , ans[MAXN + 1] , niv[MAXN + 1] , cnt , idx[MAXN + 1];
vector< int >edges[MAXN + 1];
vector< unsigned short >path[MAXN + 1];
vector< int >v;
int f[MAXN + 1];
void init() {
    int i , j;
    for( i = 1 ; i <= n ; i++ )
        up[0][i] = par[i];
    for( j = 1 ; j < LOG ; j++ )
        for( i = 1 ; i <= n ; i++ )
            up[j][i] = up[j - 1][up[j - 1][i]];
}
void dfs( int nod , int p ) {
    par[nod] = p;
    niv[nod] = niv[p] + 1;
    for( auto x : edges[nod] )
        if( x != p )
            dfs( x , nod );
}
int kth( int nod , int k ) {
    int i;
    //cout << nod - 1 << ' ';
    for( i = 0 ; ( 1 << i ) <= k ; i++ )
        if( ( 1 << i ) & k )
            nod = up[i][nod];
    //cout << nod - 1 << '\n';
    return nod;
}
void updnode( int st , int dr , int val ) {
    //cout << st << ' ' << dr << ' ' << t << ' ' << val << '\n';
    while( st != dr ) {
        //cout << st << '\n';
        v.push_back( st );
        st = par[st];
    }
    if( val == 0 )
        v.push_back( st );
    else
        reverse( v.begin() , v.end() );
    //cout << t << ' ' << st << '\n';
}
void lca( int a , int b , int t , int what ) {
    int nod , i , cop1 , cop2;
    cop1 = a;
    cop2 = b;
    if( niv[a] < niv[b] )
        swap( a , b );
    a = kth( a , niv[a] - niv[b] );
    for( i = LOG - 1 ; i >= 0 ; i-- )
        if( up[i][a] != up[i][b] ) {
            a = up[i][a];
            b = up[i][b];
        }
    if( a != b ) {
        a = up[0][a];
        b = up[0][b];
    }
    nod = a;
    a = cop1;
    b = cop2;
    //cout << a << ' ' << b << ' ' << nod << '\n';
    if( what == 0 ) {
        updnode( a , nod , 0 );
        for( auto x : v )
            path[cnt].push_back( x );
        v.clear();
        //cout << '\n';
        updnode( b , nod , 1 );
        for( auto x : v )
            path[cnt].push_back( x );
        v.clear();
    }
}
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 i , j , m = D.size() , t;
    n = R.size() + 1;
    vector< int >rasp;
    for( auto [ a , b ] : R ) {
        a++;
        b++;
        edges[a].push_back( b );
        edges[b].push_back( a );
    }
    dfs( 1 , 0 );
    init();
    for( i = 0 ; i < m ; i++ ) {
        S[i]++;
        T[i]++;
    }
    cnt = 1;
    for( i = 0 ; i < m ; i++ ) {
        lca( S[i] , T[i] , D[i] , 0 );
        cnt++;
    }
    for( i = 1 ; i <= m ; i++ ) {
        ans[i] = -1;
        if( I[i - 1] == 1 )
            ans[i] = D[i - 1];
    }
    for( i = 1 ; i <= n ; i++ )
        f[i] = -1;
    for( t = 0 ; t <= 1e6 ; t++ ) {
        for( i = 1 ; i <= m ; i++ ) {
            if( idx[i] < path[i].size() )
                break;
        }
        if( i == m + 1 )
            break;
        for( i = 1 ; i <= m ; i++ ) {
            if( idx[i] == path[i].size() )
                continue;
            if( t < D[i - 1] )
                continue;
            if( I[i - 1] == 1 ) {
                //cout << i << ' ' << t << '\n';
                f[path[i][idx[i]]] = t;
                //cout << path[i][idx[i]] << ' ' << t << '\n';
                //cout << path[i][idx[i]] << ' ' << t << '\n';
            }
        }
        for( i = 1 ; i <= m ; i++ ) {
            if( idx[i] == path[i].size() )
                continue;
            if( t < D[i - 1] )
                continue;
            if( I[i - 1] )
                continue;
            if( f[path[i][idx[i]]] == t ) {
                I[i - 1] = 1;
                ans[i] = t;
            }
        }
        for( i = 1 ; i <= m ; i++ ) {
            if( idx[i] == path[i].size() )
                continue;
            if( t < D[i - 1] )
                continue;
            idx[i]++;
        }
    }
    for( i = 1 ; i <= m ; i++ ) {
        if( ans[i] == -1 )
            ans[i] = 0;
        else {
            //cout << ans[i] << ' ';
            ans[i] -= D[i - 1];
            ans[i] = path[i].size() - ans[i];
            //cout << ans[i] << '\n';
        }
        rasp.push_back( ans[i] );
    }
    return rasp;
}
