版权声明

本题版权归 Long Long OJ 所有。

题目描述

现有一张 $n$ 个点的无向图。这张无向图共有 $m$ 条边，边权分别为 $1,2,\ldots,m$。

现有 $q$ 个询问，每个询问都是如下形式：如果（询问间互相不影响）对这张图进行操作，只保留（其他的边将会被删去）图中保留边权为 $x,x+1,\ldots,y$ 的边（共有 $\bm{y-x+1}$ 条），那么操作后的图中共有多少个连通块？

输入格式

• 第一行：$n,m,q$，表示图的点数，边数，以及询问数。
• 第 $2\sim m+1$ 行，每行两个整数 $l,r$，表示一条边，从点 $l$ 连到点 $r$。保证 $1 \le l,r \le n$。按照输入顺序，这 $\bm m$ 条边的边权依次为 $\bm{1,2,\ldots,m}$。
• 第 $m+2\sim m+q+1$ 行，每行两个整数 $x,y$，表示一个询问。保证 $1 \le x \le y \le m$。
• 图中可能有重边或自环。

输出格式

$q$ 行，表示每组询问的答案。

样例

5 5 5
1 3
2 4
2 5
3 5
1 4
1 5
2 4
2 5
3 3
3 5

1
2
1
4
2

提示

• 对于 $10\%$ 的数据，$1\leq n,m,q \leq 10$；
• 对于 $20\%$ 的数据，$1\leq n,m,q\leq 500$；
• 对于 $30\%$ 的数据，$1\leq n,m,q\leq 5000$；
• 对于另外 $5\%$ 的数据，$x=1,y=m$；
• 对于 $100\%$ 的数据，$1\leq n,m,q\leq 10^5$。