#include "infection.h"
#include <vector>
#include <iostream>
#include <utility>
#include <queue>
#include <map>
#include <cmath>
#include <algorithm>
using namespace std;
vector<int>sol;
vector<int long long>v[150100];
int long long x,y,q,n,tt[150100],niv[150100],r,d,s,ok,t,i1,i2,a[150100],b[150100],ok1,r1,p1,p2,root,h,z[30000000],zl,d1,poz,C[150100],rsp[150100],l,p;
int TT[150100][25],ss[150100];
struct query
{
    int long long d,s,t,ok;
}Q[150100];
queue<int long long>Qu;
vector<int> solve( vector<pair<int, int>> R, vector<long long> D, vector<int> S, vector<int> T, vector<bool> I)
{
    while (R.size())
    {
       x=R.back().first;
       y=R.back().second;
       x++;
       y++;
       v[x].push_back(y);
       v[y].push_back(x);
       n++;
       R.pop_back();
    }
    n++;
    while (D.size())
    {
        q++;
        Q[q].d=D.back();
        Q[q].s=S.back()+1;
        Q[q].t=T.back()+1;
        Q[q].ok=I.back();
        D.pop_back();
        S.pop_back();
        T.pop_back();
        I.pop_back();
    }
    Qu.push(1);
    tt[1]=1;
    while (Qu.size())
    {
        x=Qu.front();
        Qu.pop();
        for (auto i:v[x])
        if (tt[i]==0) tt[i]=x,niv[i]=niv[x]+1,Qu.push(i);
    }
    tt[1]=0;
    for (int i=1; i<=n; i++)
    TT[i][0]=tt[i];
    for (int j=1; j<=20; j++)
    for (int i=1; i<=n; i++)
    TT[i][j]=TT[TT[i][j-1]][j-1];


    for (int i=1; i<=q; i++)
    {
        d=Q[i].d;
        s=Q[i].s;
        t=Q[i].t;
        ok=Q[i].ok;
        C[q-i+1]=ok;
        r=0;
        i1=i2=0;

        p1=s;
        p2=t;

        for (int j=20; j>=0; j--)
        if (niv[p1]-pow(2,j)>=niv[p2]) p1=TT[p1][j],r=r+pow(2,j);

        for (int j=20; j>=0; j--)
        if (niv[p2]-pow(2,j)>=niv[p1]) p2=TT[p2][j],r=r+pow(2,j);


        for (int j=20; j>=0; j--)
        if (TT[p1][j]!=TT[p2][j]) p1=TT[p1][j],p2=TT[p2][j],r=r+pow(2,j)*2;

        if (p1!=p2) r=r+2;
        r++;
        ss[q-i+1]=r;
    }
    for (int i=1; i<=q; i++)
    sol.emplace_back(ss[i]);

    return sol;
}/*

signed main()
{
    int n, m;

    cin >> n;
    cin >> m;

    vector<pair<int, int>> edges = {};
    vector<long long> day;
    vector<int> start;
    vector<int> target;
    vector<bool> infected;

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        edges.emplace_back(u, v);
    }

    for (int i = 0; i < m; i++) {
        long long _d, _s, _t, _i;
        cin >> _d >> _s >> _t >> _i;
        day.push_back(_d);
        start.push_back(_s);
        target.push_back(_t);
        infected.push_back(_i);
    }

    const auto ans = solve(edges, day, start, target, infected);
    for (const auto it : ans) {
        std::cout << it << std::endl;
    }

    return 0;
}
*/
