ZS 的 "99" 雷达 (ZS's "99" Radar)

题目背景

在青春洋溢的校园里，ZS 是一位热心肠且自带“CP 雷达”的同学。每当他在校园里捕捉到一对甜蜜的 CP（情侣），他都会送上最诚挚的祝福：“99！”（意为长长久久）。

题目描述

校园里一共有 $N$ 名同学，编号从 $1$ 到 $N$。 ZS 经过长期的潜伏观察，记录下了校园里的 $M$ 条“双向暧昧关系”。第 $i$ 条关系连接了编号为 $u_i$ 和 $v_i$ 的同学。

ZS 虽然热衷于磕 CP，但他极其讨厌到处撒网的“海王”。他定义一对“真爱 CP”必须满足以下两个条件：

1. 这两个人之间存在一条“暧昧关系”。
2. 在全局的所有关系中，这两个人都没有任何其他的暧昧对象。（换句话说，这两人在这 $M$ 条关系中，都只与对方有且仅有一条关系）。

ZS 每捕捉到一对“真爱 CP”，就会大喊一次“99”。

最近，校园里要举办各种社团联谊活动。一共有 $Q$ 场活动，第 $i$ 场活动只邀请了编号在 $L_i$ 到 $R_i$ 之间的同学参加。 同学们很崩溃，一直被 ZS 喊“99”，但是他们不知道 ZS 一共喊了多少次“99”，请你编写程序，帮同学们计算出 ZS 在每一场活动中，会喊出多少次“99”。

注意：判断是否为“真爱 CP”的标准依据的是全局的 $M$ 条关系。如果某人在全局是个“海王”，哪怕参加活动的同学中只有他的一名暧昧对象，他也不会被 ZS 承认为真爱 CP。

输入格式

第一行包含三个整数 $N, M, Q$，分别表示同学总数、暧昧关系总数和活动（询问）的场数。 接下来 $M$ 行，每行两个整数 $u, v$，表示编号为 $u$ 和 $v$ 的同学之间有一条双向暧昧关系。（图中可能包含重边，若出现多次同一对暧昧关系，视为多条边，意味着他们也不算纯粹的真爱）。 接下来 $Q$ 行，每行两个整数 $L, R$，表示一场活动邀请的同学编号范围。

输出格式

输出 $Q$ 行，每行一个整数，表示 ZS 在第 $i$ 场活动中会喊出“99”的次数。

输入输出样例

输入样例 #1

8 5 4
1 2
3 4
5 6
7 8
5 7
1 8
3 4
1 4
4 6

输出样例 #1

2
1
2
0

说明/提示

全局各同学的暧昧对象数量（度数）：

• 同学 1：与 2 暧昧，度数 1。
• 同学 2：与 1 暧昧，度数 1。
• 同学 3：与 4 暧昧，度数 1。
• 同学 4：与 3 暧昧，度数 1。
• 同学 5：与 6、7 暧昧，度数 2（海王！）。
• 同学 6：与 5 暧昧，度数 1。
• 同学 7：与 8、5 暧昧，度数 2（海王！）。
• 同学 8：与 7 暧昧，度数 1。

可见，全局只有两对“真爱 CP”：(1, 2) 和 (3, 4)。

• 询问 1：区间 [1, 8] 包含了 (1, 2) 和 (3, 4)，大喊 2 次 99。
• 询问 2：区间 [3, 4] 仅包含了 (3, 4)，大喊 1 次 99。
• 询问 3：区间 [1, 4] 包含了 (1, 2) 和 (3, 4)，大喊 2 次 99。
• 询问 4：区间 [4, 6]，虽然包含了同学 4、5、6，但没有任何一对完整的真爱 CP 都在这个区间内，输出 0。

数据规模与约定

• 对于 $30\%$ 的数据，$1 \le N, M, Q \le 2000$。
• 对于 $100\%$ 的数据，$2 \le N \le 10^5$，$1 \le M \le 2 \times 10^5$，$1 \le Q \le 10^5$，$1 \le u, v \le N, u \neq v$，$1 \le L \le R \le N$。