Feasible Event Pairs in a DAG of Spacetime

Dream abstracts spacetime as a rooted directed tree with \(n\) nodes where the root is node \(1\) and every edge is directed from a shallower node to a deeper node. Then, using his superpower, Dream adds \(m\) extra directed edges on this tree; however, the final graph remains a Directed Acyclic Graph (\(DAG\)).

He further abstracts an event as a node in the graph and 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 whose last event is \(j\). (Note that a simple path is defined as a path with no repeated vertices and, in this problem, we only count the pairs with \(i \neq j\)).

You are given \(q\) queries. The \(i\)th query is represented by two integers \(l_i\) and \(r_i\) (with \(l_i \le r_i\)). For each query, count the number of feasible pairs \((i,j)\) with \(i,j \in [l_i, r_i]\). In other words, count the number of ordered pairs \((i, j)\) with \(l_i \le i,j \le r_i\) and \(i\) can reach \(j\) via a simple path in the graph, where we do not count the trivial pair \(i = j\).

The input graph is given in the following format:

• The tree structure is provided by \(n-1\) integers: \(p_2, p_3, \ldots, p_n\), where for each \(2 \le i \le n\), there is a tree edge from \(p_i\) to \(i\). (Since the tree is rooted at node \(1\), it is guaranteed that \(p_i < i\).)
• Then \(m\) extra edges are given. Each extra edge is represented by two integers \(u\) and \(v\), indicating an edge from \(u\) to \(v\). It is guaranteed that adding these edges still results in a DAG.

You must answer each query efficiently.

Note on Formalism:

In summary, let \(\text{reach}(i)\) denote the set of nodes reachable from node \(i\) (with \(i\) itself included via the trivial path). We define the count for a query \([l,r]\) as \(\displaystyle \sum_{i=l}^{r} \Big(|\text{reach}(i) \cap \{l, l+1, \ldots, r\}| - 1\Big)\), where the \(-1\) removes the trivial self-reachability.

inputFormat

The first line contains three positive integers \(n,m,q\) representing the number of nodes, the number of extra edges, and the number of queries.

The second line contains \(n-1\) integers: \(p_2, p_3, \ldots, p_n\), where \(p_i\) is the parent of node \(i\) in the tree (\(1 \le p_i < i\)).

The following \(m\) lines each contain two integers \(u\) and \(v\) representing an extra directed edge from \(u\) to \(v\).

The next \(q\) lines each contain two integers \(l_i\) and \(r_i\) (with \(l_i \le r_i\)), representing a query.

outputFormat

For each query, output a single line containing one integer: the number of feasible event pairs \((i,j)\) (with \(i\neq j\)) such that both \(i\) and \(j\) belong to the query interval \([l_i, r_i]\) and there exists a path from \(i\) to \(j\) in the graph.

sample

5 2 3
1 1 3 3
2 4
2 5
1 3
2 5
3 5

2
4
2

</p>