题目描述

Dream 将时空抽象为一颗 $n$ 节点有向有根树，其中树根为节点 $1$ 并且所有边的方向都为浅往深。
Dream 用他的超能力在这颗树上额外添加 $m$ 条有向边，但最终的图仍然是无环图。
Dream 进而将一个事件抽象为图上的一个节点，将一个时代抽象为图上的一个简单路径。
Dream 认为一对事件 $(i,j)$ 可行 当且仅当存在一个时代，使得时代的首事件是 $i$，末事件是 $j$。
Dream 不满足于统计普通可行对。他认为超能力添加的额外边十分重要。
Dream 认为一对事件 $(i,j)$ 条件可行 当且仅当 $(i,j)$ 可行并且所有额外边去掉之后 $(i,j)$ 非可行。
Dream 现在有 $q$ 组询问。第 $i$ 组询问用两个正整数 $l_i$ 与 $r_i$ 表示，其中 $l_i\le r_i$。
Dream 想知道，对每一组询问，有多少对 条件可行 事件 $(i,j)$，使得 $l\le i<j\le r$。

输入格式

第一行两个整数 $n,m$。
接下来一行 $n-1$ 个正整数描述树的结构。第 $i$ 个数代表 $i+1$ 号节点的父亲的编号 $f_i$，也就是说存在一个 $f_i$ 往 $i$ 的一条边。
接下来 $m$ 行，每行两个正整数 $u,v$，表示一条 $u$ 往 $v$ 额外添加的边。
接下来一个正整数 $q$。
接下来 $q$ 行，每行两个正整数 $l,r$，表示一组询问。

输出格式

输出 $q$ 行，每行一个整数，表示对应组询问的答案。

2 2
1
1 2
1 2
1
1 2

0

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

0
1
4

提示

• Subtask 1（3 pts）：$n,q\le 1000$，3s；
• Subtask 2（29 pts）：$n,q\le2\times10^5$，$m\le50$，3s；
• Subtask 3（31 pts）：$m\le 50$，5s；
• Subtask 4（37 pts）：无额外限制，5s。

对于 $100\%$ 的数据，$2\le n\le7\times10^5$，$1\le q\le3\times10^5$，$0\le m\le100$。