Shared code

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 2e5 + 1, MOD = 1e9 + 7;

int n, m, q;
vector<pii> edges;

struct dsu {
	int ccc = 0; // Connected Components Count
	int cnt[N], par[N];
	inline void init(int sz) {
		ccc = sz;
		for (int i = 0; i <= sz; i++) {
			par[i] = i;
			cnt[i] = 1;
		}
	}
	int root(int node) {
		if (par[node] == node) return node;
		return root(par[node]);
	}
	bool link(int x, int y) {
		x = root(x);
		y = root(y);
		if (cnt[x] < cnt[y]) swap(x, y);
		if (x == y)
			return false;
		par[y] = x;
		cnt[x] += cnt[y];
		ccc--;
		return true;
	}
};

struct pbs {
public:
	int idx, l, r;
	int a, b;
	int Naser_md() {
		return (l + r) / 2;
	}
} qrs[N];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		if (a > b) swap(a, b);
		edges.push_back({ a, b });
	}

	for (int i = 0; i < q; i++) {
		cin >> qrs[i].a >> qrs[i].b;
		qrs[i].idx = i;
		qrs[i].l = 1, qrs[i].r = m + 1;
	}
	dsu cur;
	int lg = ceil(log2(m));
	while (lg--)
	{
		cur.init(n);
		sort(qrs, qrs + q, [](const pbs& x, const pbs& y) {
			return (x.l + x.r) / 2 < (y.l + y.r) / 2;
			});
		int idx = 0;
		for (int i = 0; i < m; i++) {
			cur.link(edges[i].first, edges[i].second);
			while (idx < q && qrs[idx].Naser_md() == i + 1) {
				if (qrs[idx].l >= qrs[idx].r) {
					idx++;
					continue;
				}
				if (cur.root(qrs[idx].a) == cur.root(qrs[idx].b))
					qrs[idx].r = qrs[idx].Naser_md();
				else
					qrs[idx].l = qrs[idx].Naser_md() + 1;
				idx++;
			}
			if (idx == q) break;
		}
	}
	sort(qrs, qrs + q, [](const pbs& x, const pbs& y) {
		return x.idx < y.idx;
		});
	for (int i = 0; i < q; i++)
		cout << (qrs[i].l == m + 1 ? -1 : (qrs[i].a == qrs[i].b ? 0 : qrs[i].l)) << '\n';
}