#include <bits/stdc++.h> #define F first #define S second using namespace std; typedef long long ll; typedef pair<int, int> pii; int n, m, k; pii edges[30001]; int pa[2][2001]; int root(int u, int ty) { if (pa[ty][u] < 0) return u; return pa[ty][u] = root(pa[ty][u], ty); } bool samer(int u, int v, int ty) { return (root(u, ty) == root(v, ty)); } bool unco(int u, int v, int ty) { if (!samer(u, v, ty)) { int pu = root(u, ty), pv = root(v, ty); if (pa[ty][pu] > pa[ty][pv]) swap(pu, pv); pa[ty][pu] += pa[ty][pv]; pa[ty][pv] = pu; return true; } return false; } bool unco2(int id, int ty) { return unco(edges[id].F, edges[id].S, ty); } bool samer2(int id, int ty) { return (root(edges[id].F, ty) == root(edges[id].S, ty)); } vector<int> e1, e2; int res[2001][2001]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("in.inp", "r", stdin); // freopen("out.out", "w", stdout); cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> edges[i].F >> edges[i].S; } // Build forest for (int i = 1; i <= n; i++) pa[0][i] = -1; for (int i = 1; i <= m; i++) { if (unco2(i, 0)) { e1.push_back(i); } } for (int i = 1; i <= n; i++) pa[0][i] = -1; for (int i = m; i >= 1; i--) { if (unco2(i, 0)) { e2.push_back(i); } } // Debug // cout << e1.size() << " " << e2.size() << "\n"; // build res for (int i = 1; i <= n; i++) pa[0][i] = -1; int ipe = n; for (int i = 0; i <= e1.size(); i++) { if (i > 0) { unco2(e1[i - 1], 0); ipe--; } int ipe2 = ipe; for (int i = 1; i <= n; i++) pa[1][i] = pa[0][i]; for (int j = 0; j <= e2.size(); j++) { if (j > 0) { if (!samer2(e2[j - 1], 1)) { unco2(e2[j - 1], 1); ipe2--; } } res[i][j] = ipe2; if (res[i][j] <= 0) cout << i << " " << j << " -> " << res[i][j] << "\n"; } } // Process cin >> k; while (k--) { int ls, rs; cin >> ls >> rs; int l, r, ans1, ans2; // Find l = 1; r = e1.size(); ans1 = 0; while (l <= r) { int mid = (l + r) / 2; if (e1[mid - 1] < ls) { l = mid + 1; ans1 = mid; } else r = mid - 1; } l = 1; r = e2.size(); ans2 = 0; while (l <= r) { int mid = (l + r) / 2; if (e2[mid - 1] > rs) { l = mid + 1; ans2 = mid; } else r = mid - 1; } // Print cout << res[ans1][ans2] << "\n"; } return 0; }