E. Dream and the Multiverse
time limit per test
8 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

source: https://youtu.be/tylNqtyj0gs

I have gone over the scenarios in my head,

and there are 6.96969 billion outcomes, and only one of them -

- do I win.

Dream abstracts the fabric of spacetime as a directed rooted tree (arborescence) with $$$N$$$ nodes (numbered $$$1$$$ through $$$N$$$). Node $$$1$$$ is the root and for each $$$i$$$ ($$$1 \le i \le N-1$$$), the parent of node $$$i+1$$$ is $$$f_i$$$. All edges of this tree are directed away from the root.

Then, Dream employs a magical superpower and adds $$$M$$$ directed edges to this tree in such a way that the resulting directed graph remains acyclic (a DAG).

Let's call a node of this DAG an event and further call a simple path on this DAG an era. Dream considers a pair of events $$$(i,j)$$$ to be plausible if there is an era whose first event is $$$i$$$ and last event is $$$j$$$. Note that $$$i \lt j$$$ does not have to hold for a plausible pair.

Dream now wants you to answer $$$Q$$$ queries. In each query, he gives you two positive integers $$$l$$$ and $$$r$$$, where $$$l \leq r$$$, and he wishes to know the number of plausible pairs of events $$$(i,j)$$$ such that $$$l \leq i,j \leq r$$$.

Input

The first line of the input contains two integers $$$N$$$ and $$$M$$$ ($$$2\le N\le 10^5$$$, $$$0\le M\le 10^5$$$).

The second line contains $$$N-1$$$ integers $$$f_1, f_2, \ldots, f_{N-1}$$$, the $$$i$$$-th of which is the father of node $$$i+1$$$. Note that $$$f_i \lt i+1$$$ does not necessarily hold!

$$$M$$$ lines follow. Each of these lines contains two integers $$$u$$$ and $$$v$$$, describing an additional edge from node $$$u$$$ to node $$$v$$$.

The following line contains a single integer $$$Q$$$ ($$$1\le Q\le 10^6$$$).

$$$Q$$$ lines follow. Each of these lines contains two integers $$$l$$$ and $$$r$$$ ($$$l\le r$$$), describing a query.

Output

For each query, print a single line containing one integer — the number of plausible pairs $$$(i,j)$$$ such that $$$l \leq i,j \leq r$$$.

Scoring
  • In the zeroth subtask, worth $$$0$$$ points, the tests are the samples shown above.
  • In the first subtask, worth $$$1$$$ point, the tree forms a line; that is, there exists a permutation that describes a simple path on this tree.
  • In the second subtask, worth $$$11$$$ points, $$$n,q,m\le1000$$$.
  • In the third subtask, worth $$$7$$$ points, $$$m\le 5$$$.
  • In the fourth subtask, worth $$$23$$$ points, $$$n,q,m\le5\times10^4$$$.
  • In the fifth subtask, worth $$$17$$$ poitns, $$$q\le 10^5$$$.
  • In the sixth subtask, worth $$$41$$$ points, no additional restrictions are imposed.
Examples
Input
2 2
1
1 2
1 2
1
1 2
Output
3
Input
8 2
1 2 5 1 4 3 3
2 4
4 7
3
4 6
5 7
1 8
Output
6
5
27
Note

In the first sample, the plausible pairs are $$$(1,1)$$$, $$$(1,2)$$$, and $$$(2,2)$$$.

In the second sample, the plausible pairs that contribute to the second query are $$$(5,5)$$$, $$$(5,6)$$$, $$$(5,7)$$$, $$$(6,6)$$$, and $$$(6,7)$$$.