U715752 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：与 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$。