#include "infection.h"
#include <vector>
#include <iostream>
#include <utility>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
vector<int>sol;
vector<int long long>v[5100];
int long long x,y,q,n,tt[5100],niv[5100],r,d,s,ok,t,i1,i2,a[5100],b[5100],ok1,r1,p1,p2,root,h,z[26000000],zl,d1,poz,C[5100],rsp[5100],l,p;
struct zile
{
    int node,query,zi;
}zz[26000000];
bool ord (zile a,zile b)
{
    return a.zi<b.zi;
}
struct query
{
    int long long d,s,t,ok;
}Q[150100];
queue<int long long>Qu;
unordered_map<int long long,int>mp;
unordered_map<int long long,int>ma;
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);
    }

    for (int i=1; i<=q; i++)
    {
        for (int j=Q[i].d; j<=Q[i].d+n; j++)
        z[++i1]=j;
    }
    sort (z+1,z+i1+1);
    for (int i=1; i<=i1; i++)
    if (ma[z[i]]==0) poz++,ma[z[i]]=poz;

    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;
        while (niv[p1]>niv[p2]) p1=tt[p1];
        while (niv[p2]>niv[p1]) p2=tt[p2];
        while (p1!=p2) p1=tt[p1],p2=tt[p2];

        root=p1;
        p1=s;
        p2=t;
        while (p1!=root) a[++i1]=p1,p1=tt[p1];
        while (p2!=root) b[++i2]=p2,p2=tt[p2];
        a[++i1]=root;
        for (int j=i2; j>=1; j--)
        a[++i1]=b[j];
        for (int p=1; p<=i1; p++)
        {
            d1=ma[d];
            d++;
            zz[++l].node=a[p];
            zz[l].query=q-i+1;
            zz[l].zi=d1;

            /*h=s*(n+1)+d;
            if (mp[h]) ok=1;
            if (ok) r++,mp[h]=1;
            s=tt[s];*/
        }
    }
    sort (zz+1,zz+l+1,ord);
    p=1;
    for (int i=1; i<=poz; i++)
    {
        p1=p;
        while (zz[p1].zi==i && p1<=l)
        {
            if (C[zz[p1].query])
            {
                h=zz[p1].node*(l+1)+i;
                mp[h]=1;
            }
            p1++;
        }

        while (zz[p].zi==i && p<=l)
        {
            h=zz[p].node*(l+1)+i;
            if (mp[h]) C[zz[p].query]=1;
            if (C[zz[p].query]) rsp[zz[p].query]++;
            p++;
        }
    }
    for (int i=1; i<=q; i++)
    sol.emplace_back(rsp[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;
}
*/

