#include "infection.h"
#include <vector>
#include <utility>
#include <iostream>
#include <map>
#include <random>
#include <chrono>
#include <set>
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define V vector
#define rep(a, b, c, d) for (int a = b; a <= c; a += d)
#define repl(a, b, c, d) for (int a = b; a >= c; a -= d)
#define pb push_back
#define ll long long 
#define all(v) v.begin(), v.end()
#define sz(x) int(x.size())

using namespace std;

const int N = 2e5 + 5;
const int LG = 18;
int d[N];
int up[N][LG + 1];
V<int> adj[N];

void dfs(int node, int p) {
    for (auto i : adj[node]) if (i != p) {
        up[i][0] = node;
        d[i] = d[node] + 1;
        rep(j, 1, LG, 1)
            up[i][j] = up[up[i][j - 1]][j - 1];
        dfs(i, node);
    }
}

int lca(int a, int b) {
    if (d[a] < d[b]) {
        swap(a, b);
    }
    int ds = d[a] - d[b];
    rep(i, 0, LG, 1) if (ds & (1 << i)) {
        a = up[a][i];
    }
    if (a == b)
        return a;
    repl(i, LG, 0, 1) {
        if (up[a][i] != up[b][i]) {
            a = up[a][i], b = up[b][i];
        }
    }
    return up[a][0];
}

V<int> w(int s, int dd) {
    int l = lca(s, dd);
    V<int> lf, rg;
    while (s != l) {
        lf.pb(s);
        s = up[s][0];
    }
    lf.pb(l);
    while (dd != l) {
        rg.pb(dd);
        dd = up[dd][0];
    }
    reverse(all(rg));
    for (auto i : rg)
        lf.pb(i);

    return lf;
}


std::vector<int> solve(
    std::vector<std::pair<int, int>> R,
    std::vector<long long> a,
    std::vector<int> s,
    std::vector<int> t,
    std::vector<bool> good
) {
    int n = sz(s);
    int m = sz(R) + 1;
   
    for (auto x : R) {
        adj[x.first].pb(x.second);
        adj[x.second].pb(x.first);
    }

    /*rep(i, 0, LG, 1)
        up[1][i] = 1;
    d[1] = 1;*/
    //return {};

    dfs(0, 0);

    /*rep(i, 0, m - 1, 1) {
        cout << d[i] << " ";
    }
    cout << endl;

    rep(i, 0, m - 1, 1) {
        rep(j, 0, LG, 1) {
            cout << up[i][j] << " ";
        }
        cout << endl;
    }

    rep(i, 0, m - 1, 1) {
        rep(j, 0, m - 1, 1) {
            cout << i << " " << j << " " << lca(i, j) << endl;
        }
    }
    return {};
    */
    V< int > dst(n, 0);
    V<int> ans(n, 0);
    rep(i, 0, n - 1, 1) {
        dst[i] = d[s[i]] + d[t[i]] - 2 * d[lca(s[i], t[i])] + 1;
    }
    //return ans;

    V<V<int>> way(n);
    
    rep(i, 0, n - 1, 1) {
        way[i] = w(s[i], t[i]);
    }
    rep(i, 0, n - 1, 1) if (good[i]) {
        ans[i] = sz(way[i]);
    }
    V<int> pos(n, -1);
    rep(i, 0, n - 1, 1)
        pos[i] = s[i];

    set <int> gd, bd;
    rep(i, 0, n + m, 1) {
        V<bool> vr(m + 1, false);
        rep(j, 0, n - 1, 1) {
            if (pos[j] != -1) {
                if (sz(way[j]) > i) {
                    pos[j] = way[j][i];
                }
                else
                    pos[j] = -1;
            }

            if (good[j] && pos[j] != -1) {
                vr[pos[j]] = true;
            } 
        }
        rep(j, 0, n - 1, 1) 
            if (pos[j] != -1) {
                
                if (vr[pos[j]] && !good[j]) {
                    good[j] = 1;
                    ans[j] = sz(way[j]) - i;
                }
            }
    }
    return ans;
}
