将询问离线下来,按右端点排序,用 LCT 维护割边并用树状数组查询即可。

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

inline int read() {
	int x = 0, f = 0; char ch = getchar();
	while (ch < '0' or ch > '9') f |= (ch == '-'), ch = getchar();
	while (ch >= '0' and ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

int __stk[128], __top;
inline void write(int x) {
    if(x < 0) putchar('-'), x = -x;
	do { __stk[++__top] = x % 10, x /= 10; } while (x);
	while (__top) putchar(__stk[__top--] + '0');
}

const int mod = 998244353;

void Min(int &x, int y) { y < x and (x = y); }
void Max(int &x, int y) { y > x and (x = y); }

void inc(int &x, int y) { (x += y) >= mod and (x -= mod); }
void mul(int &x, int y) { x = 1ll * x * y % mod; }

int q_pow(int x, int k) { int res = 1; for (; k; k >>= 1, mul(x, x)) if (k & 1) mul(res, x); return res; }

bool stmer;

const int N = 4e5 + 10;

struct edge {
    int u, v;
} e[N];

struct Query {
    int l, id;
};

int n, m, q;
int ans[N];

vector<Query> op[N];

namespace BIT {
    int t[N];

    void add(int x, int k) { while (x) t[x] += k, x -= x & -x; }
    int ask(int x) { int res = 0; while (x <= m) res += t[x], x += x & -x; return res; }
}

namespace LCT {
    int top;
    int fa[N], t[N][2], a[N], s[N], tag[N];
    int stk[N];

    bool nrt(int x) { return t[fa[x]][0] == x or t[fa[x]][1] == x; }
    int get(int x) { return t[fa[x]][1] == x; }

    void reverse(int x) { swap(t[x][0], t[x][1]), tag[x] ^= 1; }
    void pushdown(int x) { if (tag[x]) reverse(t[x][0]), reverse(t[x][1]), tag[x] = 0; }

    void update(int x) { s[x] = min({ s[t[x][0]], s[t[x][1]], a[x] }); }

    void rotate(int x) {
        int f1 = fa[x], f2 = fa[f1], k = get(x);
        if (nrt(f1)) t[f2][get(f1)] = x; fa[x] = f2;
        t[f1][k] = t[x][!k], fa[t[f1][k]] = f1;
        t[x][!k] = f1, fa[f1] = x;
        update(f1), update(x);
    }

    void splay(int x) {
        int p = stk[++top] = x;
        while (nrt(p)) stk[++top] = p = fa[p];
        while (top) pushdown(stk[top--]);
        for (int f = fa[x]; nrt(x); rotate(x), f = fa[x])
            if (nrt(f)) rotate(get(x) == get(f) ? f : x);
    }

    void access(int x) {
        int f = 0;
        while (x) splay(x), t[x][1] = f, update(x), f = x, x = fa[x];
    }

    void mkrt(int x) { access(x), splay(x), reverse(x); }
    void split(int u, int v) { mkrt(u), access(v), splay(v); }
    int findrt(int x) {
        access(x), splay(x);
        while (t[x][0]) pushdown(x), x = t[x][0];
        splay(x); return x;
    }

    void link(int u, int v) { mkrt(u), fa[u] = v; }
    void cut(int u, int v) { split(u, v), fa[u] = t[v][0] = 0, update(v); }
    
    bool check(int u, int v) { mkrt(u); return findrt(v) == u; }

    void init() {
        for (int i = 0; i <= n + m; i++) {
            fa[i] = t[i][0] = t[i][1] = BIT :: t[i] = 0;
            s[i] = a[i] = i <= n ? n + m + 1 : i;
        }
    }
}

void solve() {
    n = read(), m = read(), q = read(), LCT :: init();
    for (int i = 1; i <= m; i++) e[i] = { read(), read() };

    for (int i = 1; i <= q; i++) {
        int l = read(), r = read();
        op[r].push_back({ l, i });
    }

    for (int i = 1; i <= m; i++) {
        int u = e[i].u, v = e[i].v;
        if (LCT :: check(u, v) and u != v) {
            LCT :: split(u, v);
            int x = LCT :: s[v] - n; BIT :: add(x, -1);
            LCT :: cut(e[x].u, x + n), LCT :: cut(e[x].v, x + n);
        }
        if (u ^ v) {
            BIT :: add(i, 1);
            LCT :: link(u, i + n);
            LCT :: link(i + n, v);
        }

        for (Query l : op[i]) ans[l.id] = n - BIT :: ask(l.l);

        op[i].clear();
    }

    for (int i = 1; i <= q; i++) write(ans[i]), putchar('\n');
}

bool edmer;
signed main() {
	// freopen("A.in", "r", stdin);
	// freopen("A.out", "w", stdout);
	cerr << "[Memory] " << (&stmer - &edmer) / 1024 / 1024 << " MB\n";
	
    int T = 1; while(T--) solve();

    cerr << "[Runtime] " << (double) clock() / CLOCKS_PER_SEC << " seconds\n";
	return 0;
}