#include <bits/stdc++.h>
using namespace std;
char READ_DATA;
int SIGNAL_INPUT;
template <typename Type>
inline char ru(Type &v) {
  SIGNAL_INPUT = 1;
  while ((READ_DATA = getchar()) < '0' || READ_DATA > '9')
    if (READ_DATA == '-')
      SIGNAL_INPUT = -1;
    else if (READ_DATA == EOF)
      return EOF;
  v = READ_DATA - '0';
  while ((READ_DATA = getchar()) >= '0' && READ_DATA <= '9')
    v = v * 10 + READ_DATA - '0';
  v *= SIGNAL_INPUT;
  return 1;
}
template <typename A, typename B>
inline char ru(A &x, B &y) {
  if (ru(x) == EOF) return EOF;
  ru(y);
  return 2;
}
template <typename A, typename B, typename C>
inline char ru(A &x, B &y, C &z) {
  if (ru(x) == EOF) return EOF;
  ru(y);
  ru(z);
  return 3;
}
template <typename A, typename B, typename C, typename D>
inline char ru(A &x, B &y, C &z, D &w) {
  if (ru(x) == EOF) return EOF;
  ru(y);
  ru(z);
  ru(w);
  return 4;
}
struct Edge {
  int u, v, next;
  int w, p, cap, flow;
  Edge(int _u = 0, int _v = 0, int nxt = -1, int _w = 1, int _cap = 0) {
    u = _u;
    v = _v;
    w = _w;
    cap = _cap;
    flow = 0;
    next = nxt;
  }
};
int mod = 1e9 + 7;
const int maxn = 1e6 + 2;
const double pi = acos(-1.0);
Edge edg[maxn];
int cnt, g[maxn], lst[maxn];
int n, k, m, q;
struct BIT {
  int n, t[maxn];
  void add(int x, int d) {
    while (x <= n) {
      t[x] += d;
      x += (x & -x);
    }
  }
  int sum(int x) {
    int ans = 0;
    while (x) {
      ans += t[x];
      x -= (x & -x);
    }
    return ans;
  }
} bit;
vector<int> edge[maxn];
vector<pair<int, int> > qry[maxn];
int p[maxn];
int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
int pre[maxn];
int vis[maxn], tot;
void bfs(int u, int v) {
  queue<int> q;
  q.push(u);
  vis[u] = tot;
  pre[u] = -1;
  while (!q.empty()) {
    u = q.front();
    q.pop();
    Edge *e;
    for (int i = g[u]; ~i && (e = &edg[i]); i = e->next) {
      if (vis[e->v] != tot) {
        q.push(e->v);
        pre[e->v] = i;
        vis[e->v] = tot;
        if (e->v == v) break;
      }
    }
    if (vis[v] == tot) break;
  }
  int mind = (1 << 30), mine;
  for (int i = pre[v]; ~i; i = pre[edg[i].u]) {
    if (edg[i].w < mind) {
      mind = edg[i].w;
      mine = i;
    }
  }
  u = edg[mine].u;
  v = edg[mine].v;
  if (g[u] == mine)
    g[u] = edg[mine].next;
  else {
    edg[lst[mine]].next = edg[mine].next;
    lst[edg[mine].next] = lst[mine];
  }
  mine ^= 1;
  if (g[v] == mine)
    g[v] = edg[mine].next;
  else {
    edg[lst[mine]].next = edg[mine].next;
    lst[edg[mine].next] = lst[mine];
  }
  bit.add(mind, -1);
}
int ans[maxn];
int main() {
  memset(g, cnt = -1, sizeof(g));
  memset(lst, -1, sizeof(lst));
  int x, y;
  ru(n, k);
  bit.n = n;
  for (int i = 1; i <= n; ++i) p[i] = i;
  ru(m);
  for (int i = 0; i < m; ++i) {
    ru(x, y);
    if (x > y) swap(x, y);
    edge[y].push_back(x);
  }
  ru(q);
  for (int i = 0; i < q; ++i) {
    ru(x, y);
    qry[y].push_back(pair<int, int>(i + 1, x));
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < edge[i].size(); ++j) {
      x = edge[i][j];
      y = i;
      if (find(x) == find(y)) {
        ++tot;
        bfs(x, y);
      } else {
        p[find(x)] = find(y);
      }
      if (~g[x]) lst[g[x]] = cnt + 1;
      edg[++cnt] = Edge(x, y, g[x], x), g[x] = cnt;
      if (~g[y]) lst[g[y]] = cnt + 1;
      edg[++cnt] = Edge(y, x, g[y], x), g[y] = cnt;
      bit.add(x, 1);
    }
    for (int j = 0; j < qry[i].size(); ++j) {
      ans[qry[i][j].first] = i - qry[i][j].second + 1 -
                             (bit.sum(n) - bit.sum(qry[i][j].second - 1));
    }
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
}
