Description

Dream models time and space as a rooted directed tree with $n$ nodes, where the root is node $1$ and all edges are directed from shallow to deep.
Dream uses his superpower to add $m$ extra directed edges to this tree, and the final graph is still a directed acyclic graph.
Dream further models an event as a node in the graph, and models an era as a simple path in the graph.
Dream considers a pair of events $(i,j)$ to be feasible if and only if there exists an era whose first event is $i$ and last event is $j$.
Dream now 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 feasible event pairs $(i,j)$ satisfy $i,j \in [l,r]$.

Input Format

The first line contains two integers $n,m$.
The next line contains $n-1$ positive integers describing the tree. The $i$-th number denotes the index of the parent of node $i+1$, namely $f_i$, which means there is a directed edge from $f_i$ to $i+1$.
The next $m$ lines each contain two positive integers $u,v$, indicating an extra directed edge added from $u$ to $v$.
The next line contains a positive integer $q$.
The next $q$ lines each contain two positive integers $l,r$, representing a query.

Output Format

Output $q$ lines, each containing one integer, which is the answer to the corresponding query.

2 2
1
1 2
1 2
1
1 2

3

Hint

Constraints and Notes

This problem uses bundled testdata.

• Subtask 1 (1 pts): The tree is a chain.
• Subtask 2 (11 pts): $n,q,m \le 1000$.
• Subtask 3 (7 pts): $m \le 5$.
• Subtask 4 (23 pts): $n,q,m \le 5 \times 10^4$.
• Subtask 5 (17 pts): $q \le 10^5$.
• Subtask 6 (41 pts): No special constraints.

For $100\%$ of the testdata, $2 \le n \le 10^5$, $0 \le m \le 10^5$, $1 \le q \le 10^6$.
It is guaranteed that the extra edges will not form a cycle, and the given $f_i$ form a rooted tree with root $1$.
It is guaranteed that $l \le r$.

Notes

Minecraft OI Round 4 C
idea & solution: w33z8kqrqk8zzzx33 check: ClCN

Translated by ChatGPT 5