Total destruction

main.cc

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

int get(vector<int>& parent, int v) {
	if (parent[v] == v) return v;
	return parent[v] = get(parent, parent[v]);
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> g(m);
	for (int i = 0; i < m; ++i) {
		cin >> g[i].first >> g[i].second;
		--g[i].first;
		--g[i].second;
	}

	vector<int> parent(n);
	for (int i = 0; i < n; ++i) {
		parent[i] = i;
	}
	vector<unordered_set<int>> queries(n); 
	
	int q;
	cin >> q;
	vector<int> res(q, 0);
	for (int i = 0; i < q; ++i) {
		int u, v;
		cin >> u >> v;
		--u;
		--v;
		queries[u].insert(i);
		queries[v].insert(i);
	}

	for (int i = g.size() - 1; i >= 0; --i) {
		int u = get(parent, g[i].first);
		int v = get(parent, g[i].second);
		if (u == v) {
			continue;
		}

		if (queries[u].size() > queries[v].size()) {
			swap(u, v);
		}

		for (int x : queries[u]) {
			if (queries[v].count(x)) {
				res[x] = i + 1;
				queries[v].erase(x);
			} else {
				queries[v].insert(x);
			}
		}
		parent[u] = v;
	}

	for (int i = 0; i < res.size(); ++i) {
		cout << res[i] << endl;
	}
}