Shared code

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

const int N = 200005;
int n, m, q, u[N], v[N], qu[N], qv[N], ans[N], rnd[N];

int par[N];
int fnd(int x) { return par[x] == x ? x : par[x] = fnd(par[x]); }

void bs(int l, int r, vector<int> &candi)
{
    int md = l + (r-l)/2;

    iota(par, par+n+1, 0);
    for (int i = 1; i <= md; ++i)
    {
        if (rnd[i] & 1) par[fnd(u[i])] = fnd(v[i]);
        else par[fnd(v[i])] = fnd(u[i]);
    }

    vector<int> ok, notok;
    for (auto c : candi)
    {
        if (fnd(qu[c]) == fnd(qv[c])) ok.push_back(c), ans[c] = md;
        else notok.push_back(c);
    }

    if (l != r)
    {
        bs(l, md, ok); vector<int>().swap(ok);
        bs(md+1, r, notok); vector<int>().swap(notok);
    }
}

int main() {
    srand(time(0));
    scanf("%d%d%d", &n, &m, &q);
    generate(rnd, rnd+1+n, rand);
    for (int i = 1; i <= m; ++i) scanf("%d%d", u+i, v+i);
    for (int i = 0; i < q; ++i) scanf("%d%d", qu+i, qv+i);
    fill(ans, ans+q, -1);
    vector<int> candi(q);
    iota(candi.begin(), candi.end(), 0);
    bs(1, m, candi);
    for (int i = 0; i < q; ++i) printf("%d\n", ans[i]);
}