# include <iostream>
# include <vector>
# include <tuple>
# include <algorithm>
using namespace std;
# include "infection.h"
//# include "grader.cpp"

const long long INF=1e18;
const int MAX=1e6+11,LOG=20;

int n,m;
vector<int> adj[MAX];
vector<int> adj2[MAX];
long long D[MAX];
int S[MAX];
int T[MAX];
bool I[MAX];
long long inf[MAX];
int now[MAX];
long long len[MAX];
vector<int> party[MAX];

int ct;
int id[MAX];
int sz[MAX];
int up[MAX];
int h[MAX];
void dfs_init(int curr, int par)
{
    ct++;
    id[curr]=ct;
    sz[curr]=1;

    for(int nxt: adj[curr])
    {
        if(nxt==par) continue;

        up[nxt]=curr;
        h[nxt]=h[curr]+1;
        adj2[curr].push_back(nxt);
        dfs_init(nxt,curr);
        sz[curr]+=sz[nxt];
    }
}

int st[MAX][LOG];
void sparse_table()
{
    for(int i=1;i<=n;i++) st[i][0]=up[i];
    for(int j=1;j<LOG;j++)
    {
        for(int i=1;i<=n;i++)
        {
            if(h[i]-(1<<j)<0) continue;
            st[i][j]=st[st[i][j-1]][j-1];
        }
    }
}

int get_lca(int u, int v)
{
    if(h[u]<h[v]) swap(u,v);
    for(int j=LOG-1;j>=0;j--)
    {
        if(h[u]-(1<<j)>=h[v]) u=st[u][j];
    }

    if(u==v) return u;

    for(int j=LOG-1;j>=0;j--)
    {
        if(h[u]-(1<<j)>=0 and st[u][j]!=st[v][j])
        {
            u=st[u][j];
            v=st[v][j];
        }
    }

    return st[u][0];
}

int calc(int u, int v)
{
    int lca=get_lca(u,v);
    return h[u]+h[v]-h[lca]*2;
}

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();
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        tie(u,v)=R[i];
        u++;v++;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1;i<=m;i++)
    {
        D[i]=_D[i-1];
        S[i]=_S[i-1]+1;
        T[i]=_T[i-1]+1;
        I[i]=_I[i-1];
    }
    for(int i=1;i<=m;i++)
    {
        if(I[i]) inf[i]=D[i];
        else inf[i]=INF;
        now[i]=S[i];
        len[i]=D[i];
    }

    dfs_init(1,0);
    sparse_table();

    vector<int> ans;
    for(int i=1;i<=m;i++)
    {
        if(I[i]) ans.push_back(calc(S[i],T[i])+1);
        else ans.push_back(0);
    }

    return ans;
}

