Description

Dream 将时空的结构抽象为一个有 $N$ 个节点（编号为 $1$ 到 $N$）的有向根树（树形结构）。节点 $1$ 是根节点，对于每个 $i$（$1 \le i \le N-1$），节点 $i+1$ 的父节点是 $f_i$。这棵树的所有边都是从根节点指向外部的。

然后，Dream 使用一种神奇的超能力，向这棵树中添加了 $M$ 条有向边，使得结果图仍然是无环的（有向无环图，DAG）。

我们称这个 DAG 的一个节点为一个事件，并进一步称这个 DAG 上的一条简单路径为一个时代。Dream 认为一对事件 $(i,j)$ 是可能的，如果存在一个时代，其第一个事件是 $i$，最后一个事件是 $j$。注意，对于一个可能的对，$i < j$ 并不一定成立。

Dream 现在希望你回答 $Q$ 个查询。在每个查询中，他给你两个正整数 $l$ 和 $r$，其中 $l \leq r$，他希望知道有多少对可能的事件 $(i,j)$ 满足 $l \leq i < j \leq r$。

Input Format

输入的第一行包含两个空格分隔的整数 $N$ 和 $M$。

第二行包含 $N-1$ 个空格分隔的整数 $f_1, f_2, \ldots, f_{N-1}$。

接下来的 $M$ 行中，每行包含两个空格分隔的整数 $u$ 和 $v$，描述了一条从节点 $u$ 到节点 $v$ 的额外边。

接下来的行包含一个整数 $Q$。

接下来的 $Q$ 行中，每行包含两个空格分隔的整数 $l$ 和 $r$，描述了一个查询。

Output Format

对于每个查询，输出一行，包含一个整数——满足 $l \leq i < j \leq r$ 的可能事件对 $(i,j)$ 的数量。

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

2
2
18

Hint

• $2 \leq N \leq 7 \cdot 10^5$
• $1 \leq Q \leq 7 \cdot 10^5$
• $0 \leq M \leq 20$
• 对于每个有效的 $i$，$1 \le f_i \le N$
• $1 \le u, v \le N$
• 输入描述的图是无环的
• $1 \le l \le r \le N$

子任务

子任务 #1 (17 分): $N,Q \le 3 \cdot 10^5$

子任务 #2 (83 分): 原始约束条件。

题面翻译由 ChatGPT-4o 提供。