版权声明

本题版权归 Long Long OJ 所有。

本题的时间限制为 0.1 秒。

题目描述

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

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

输入格式

第一行三个正整数 $n,m,q$，表示图的点数，边数，以及询问数。

下面 $m$ 行，每行两个正整数 $l,r$，表示一条边，从点 $l$ 连到点 $r$。

按照输入顺序，这 $\bm m$ 条边的边权依次为 $\bm{1,2,\ldots,m}$。

下面 $q$ 行，每行两个正整数 $x,y$，表示一个询问。

图中可能有重边或自环。

输出格式

$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\%$ 的数据，$n,m,q \le 10$。
• 对于 $20\%$ 的数据，$n,m,q\le 500$。
• 对于 $30\%$ 的数据，$n,m,q\le 5000$。
• 对于另外 $5\%$ 的数据，$x=1,y=m$。
• 对于 $100\%$ 的数据，$1\le n,m,q\le 10^5$，$1 \le l,r \le n$，$1 \le x \le y \le m$。