Stamp Rally - AtCoder Grand Contest 002

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

const int N = 1e5 + 5;

int n, m, q;
int par[N], cnt[N];
vector < pair<int,int> > edges;
int x[N], y[N], z[N], l[N], r[N];

int anc(int p) { return p == par[p] ? p : par[p] = anc(par[p]); }
void join(int p, int q) {
    p = anc(p), q = anc(q);
    if (p == q) return;
    par[p] = q;
    cnt[q] += cnt[p]; cnt[p] = 0;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        edges.push_back(make_pair(u, v));
    }

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

    while(true) {
        vector< pair<int,int> > events;
        for (int i = 1; i <= q; ++i) {
            if (l[i] == r[i]) continue;
            events.push_back(make_pair((l[i] + r[i]) >> 1, i));
        }
        if (events.empty()) break;
        sort(events.begin(), events.end());

        // prepare for DSU
        for (int i = 1; i <= n; ++i) par[i] = i, cnt[i] = 1;

        // solve
        int ptr = 0;
        for (int id = 1; id <= m; ++id) {
            int u = edges[id - 1].first, v = edges[id - 1].second;
            join(u, v);

            while(ptr < (int)events.size() && events[ptr].first <= id) {
                int idQuery = events[ptr].second;
                int X = anc(x[idQuery]), Y = anc(y[idQuery]);

                if (cnt[X] + (X == Y ? 0 : cnt[Y]) >= z[idQuery]) r[idQuery] = events[ptr].first;
                else l[idQuery] = events[ptr].first + 1;

                ++ptr;
            }

        }
    }

    for (int i = 1; i <= q; ++i) printf("%d\n", l[i]);
}