Stamp Rally

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

#define endl '\n'

const int N=1e5+5;

int n,m,q;
int u[N],v[N],x[N],y[N],z[N],l[N],r[N],par[N],sz[N];
vector<int> mid[N];

int get_par(int x)
{
    while(par[x]!=x)
    {
        par[x]=par[par[x]];
        x=par[x];
    }
    return x;
}

void merge(int v1,int v2)
{
    int p1=get_par(v1);
    int p2=get_par(v2);
    if(p1==p2)
    {
        return;
    }
    sz[p1]+=sz[p2];
    sz[p2]=0;
    par[p2]=p1;
}

void reset()
{
    for(int i=1;i<=n;i++)
    {
        par[i]=i;
        sz[i]=1;
    }
}

void apply(int id)
{
    merge(u[id],v[id]);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        cin>>u[i]>>v[i];
    }

    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>x[i]>>y[i]>>z[i];
        l[i]=1;
        r[i]=m;
    }

    bool done=0;
    while(!done)
    {
        done=1;
        reset();
        for(int i=1;i<=q;i++)
        {
            if(l[i]!=r[i])
            {
                done=0;
                int c_mid=(l[i]+r[i])>>1;
                mid[c_mid].push_back(i);
            }
        }

        for(int i=1;i<=m;i++)
        {
            apply(i);
            while(!mid[i].empty())
            {
                int id=mid[i].back();
                mid[i].pop_back();
                int p1=get_par(x[id]);
                int p2=get_par(y[id]);
                int sum=sz[p1];
                if(p1!=p2)
                {
                    sum+=sz[p2];
                }
                if(sum>=z[id])
                {
                    r[id]=i;
                }
                else
                {
                    l[id]=i+1;
                }
            }
        }
    }

    for(int i=1;i<=q;i++)
    {
        assert(l[i]==r[i]);
        cout<<l[i]<<endl;
    }
}