Description

警方正在筹备一次大规模的突袭行动，希望能将城市中大多数著名的犯罪分子绳之以法。为了防止信息泄露，警方内部的信息流通必须尽可能严密。每位参与行动的侦探警官（DO）都受到严格的规定约束。

DO 之间共享的信息以所谓的“滴水”（drop）形式传递。每一次滴水都是口头传递，绝不能以任何形式记录在任何媒介上，包括电子设备、纸张等。每个 DO 只能与与其有双向连接的特定 DO 共享滴水。每个 DO 有义务在收到滴水后，尽快且不做任何更改地将其传递给所有与其有连接的伙伴，除了他收到滴水的那位 DO。

总督察（CI）需要选择哪些 DO 对之间建立连接。这组最终确定的连接称为最终小组（final group，FG）。在 FG 中，还需要遵守一条额外的 FG 规则：不能出现滴水返回到曾经传递给伙伴的 DO 的情况。如果出现这种情况，说明 FG 网络中存在过多不必要的连接。

有一叠文件夹，每个文件夹描述了一对特定 DO 之间的连接。FG 的选择分为两步。首先，CI 选择两个整数 $S$ 和 $T$（有时可以相同），并从文件夹堆中移除第 $S$ 个文件夹之上的所有文件夹，以及第 $T$ 个文件夹之下的所有文件夹。

接下来，CI 对剩下的文件夹重复该操作。他选择两个整数 $U$ 和 $V$（有时可以相同），并从剩下的文件夹中移除第 $U$ 个文件夹之上的所有文件夹，以及第 $V$ 个文件夹之下的所有文件夹。

CI 希望在 FG 中使用剩下文件夹中的所有连接。然而，由于 FG 规则的限制，这些连接不一定能构成 FG。CI 经常会忘记这条规则。

CI 的职业习惯无法改变。他的助手试图通过雇佣一名程序员来逐步实现流程自动化，以委婉地解决这个问题。程序员的第一个任务是：在 CI 选择了第一步的 $S$ 和 $T$ 后，计算可能被选为 FG 的不同方案数。这个计算必须对许多不同的 $S$ 和 $T$ 都高效完成。

Input Format

第一行包含两个整数 $N$ 和 $M$（$1 \leq N, M \leq 10^5$），分别表示 DO 的数量和 CI 文件夹堆中的文件夹数量。DO 用整数 $1 \ldots N$ 编号。接下来有 $M$ 行，每行包含两个整数 $A$ 和 $B$（$1 \leq A < B \leq N$），表示该文件夹描述的 DO 对之间的连接。输入顺序即为文件夹从上到下的顺序。

下一行包含一个整数 $Q$（$1 \leq Q \leq 10^5$），表示询问的数量。接下来有 $Q$ 行，每行包含两个正整数 $S$ 和 $T$（$1 \leq S \leq T \leq M$），表示 CI 在 FG 选择第一步中选定的文件夹编号。

Output Format

对于每个询问，输出一行，表示在第二步选择过程中可以形成的不同 FG 的数量。

4 6
1 2
2 3
1 3
1 4
3 4
2 4
4
1 1
1 3
2 4
1 6

1
5
6
13

Hint

由 ChatGPT 4.1 翻译