小Y與小P

//   __________________
//  | ________________ |
//  ||          ____  ||
//  ||   /\    |      ||
//  ||  /__\   |      ||
//  || /    \  |____  ||
//  ||________________||
//  |__________________|
//  \###################\
//   \###################\
//    \        ____       \
//     \_______\___\_______\
// An AC a day keeps the doctor away.

#pragma g++ optimize("Ofast")
#pragma loop_opt(on)
#include <bits/extc++.h>
#ifdef local
#define debug(x) (cerr<<#x<<" = "<<(x)<<'\n')
#else
#include <bits/stdc++.h>
#define debug(x) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define pb emplace_back
#define ff first
#define ss second
#define mem(v,x) memset(v,x,sizeof v)

using namespace std;
using namespace __gnu_pbds;
typedef int64_t ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
constexpr ld PI = acos(-1), eps = 1e-5;
constexpr ll N = 100025, INF = 1e18, MOD = 1000000007, inf = 1e9;
constexpr inline ll cdiv(ll x, ll m) { return x/m + ((x<0 ^ m>0) && (x%m)); } // ceiling divide
constexpr inline ll modpow(ll e,ll p,ll m=MOD) {ll r=1; for(e%=m;p;p>>=1,e=e*e%m) if(p&1) r=r*e%m; return r;}

struct DSU {
    vector<pair<int,int> > ops;
    int pa[N], sz[N], tr;
    void init(int n){tr=0, iota(pa,pa+n+1,0), fill(sz,sz+n+1,1);}
    int anc(int x){return x==pa[x] ? x : anc(pa[x]);}
    void uni(int x, int y, int rec = false) {
        if((x=anc(x)) == (y=anc(y))) return;
        if(sz[x] < sz[y]) swap(x,y);
        if(rec) ops.push_back({x,y});
        ++tr, pa[y] = x, sz[x] += sz[y];
    }
    void undo(int t) {
        while(ops.size() > t) {
            int x = ops.back().first, y = ops.back().second;
            ops.pop_back();
            sz[x] -= sz[y], pa[y] = y;
        }
    }
} dsu;
vector<int> adj[N];
vector<tuple<int,int,int> > Q[N]; // Q[block[l]] == {R,L,i};
int ans[N],n,m,q;
void add(int l, int r, int i, int rec = false) { // add i -> [l,r]
    //for(int x: adj[i]) if(l <= x && x <= r) dsu.uni(i, x, rec);
    int L = lower_bound(all(adj[i]), l) - adj[i].begin();
    int R = upper_bound(all(adj[i]), r) - adj[i].begin();
    for(int j = L; j < R; j++) dsu.uni(i,adj[i][j],rec);
}
int block[N], rb[N];
signed main() {
    //freopen("in.txt", "r", stdin);
    //freopen("ou.txt", "w", stdout);
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> q;
    debug(n), debug(m), debug(q);
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    for(int i = 1; i <= n; i++) sort(all(adj[i]));
    // sigma deg == n+m*2
    for(int i = 1, cnt = 512; i <= n; i++) {
        if(cnt + adj[i].size() + 1 < 512) {
            block[i] = block[i-1];
        }else {
            block[i] = block[i-1]+1;
            cnt = 0;
        }
        cnt += adj[i].size() + 1;
        rb[block[i]] = i;
    }

    for(int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        Q[block[l]].push_back({r,l,i});
    }

    for(int b = 0; b < N; b++) if(Q[b].size()) {
        dsu.init(n);
        sort(all(Q[b]));
        int l, r = rb[b];
        for(auto p: Q[b]) {
            int i = get<2>(p);
            int R = get<0>(p), L = get<1>(p);
            l = min(R, rb[b]-1);
            while(r <= R) add(l+1,r-1,r,0), r++;
            int now = dsu.ops.size();
            int tr = dsu.tr;
            while(l >= L) add(l,R,l,1), l--;
            ans[i] = R-L+1 - dsu.tr;
            dsu.tr = tr;
            dsu.undo(now);
        }
    }
    for(int i = 0; i < q; i++) cout << ans[i] << '\n';
}