Description

Dream abstracts space-time as a rooted directed tree with $n$ nodes. The root is node $1$, and all edges are directed from shallow to deep (from ancestor to descendant).
Dream uses his superpower to add $m$ additional directed edges to this tree, but the final graph is still a directed acyclic graph (DAG).
Dream further abstracts an event as a node in the graph, and an era as a simple path in the graph.
Dream says that a pair of events $(i, j)$ is feasible if and only if there exists an era such that the first event of the era is $i$ and the last event is $j$.
Dream is not satisfied with counting ordinary feasible pairs. He believes the additional edges added by the superpower are very important.
Dream says that a pair of events $(i, j)$ is conditionally feasible if and only if $(i, j)$ is feasible, and after removing all additional edges, $(i, j)$ becomes infeasible.
Now Dream has $q$ queries. The $i$-th query is given by two positive integers $l_i$ and $r_i$, where $l_i \le r_i$.
For each query, Dream wants to know how many conditionally feasible event pairs $(i, j)$ satisfy $l \le i < j \le r$.

Input Format

The first line contains two integers $n, m$.
The next line contains $n - 1$ positive integers describing the tree structure. The $i$-th number denotes the index of the parent of node $i + 1$, $f_i$. That is, there is an edge from $f_i$ to $i + 1$.
The next $m$ lines each contain two positive integers $u, v$, denoting an additional edge directed from $u$ to $v$.
The next line contains a positive integer $q$.
The next $q$ lines each contain two positive integers $l, r$, denoting one query.

Output Format

Output $q$ lines. Each line contains one integer, the answer to the corresponding query.

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

Hint

• Subtask 1 (3 pts): $n, q \le 1000$, 3s.
• Subtask 2 (29 pts): $n, q \le 2 \times 10^5$, $m \le 50$, 3s.
• Subtask 3 (31 pts): $m \le 50$, 5s.
• Subtask 4 (37 pts): no extra constraints, 5s.

For $100\%$ of the testdata, $2 \le n \le 7 \times 10^5$, $1 \le q \le 3 \times 10^5$, $0 \le m \le 100$.

Translated by ChatGPT 5