Plausible Pairs in a DAG

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 given by \(f_i\). All tree edges are directed away from the root.

Then, Dream adds \(M\) extra directed edges to this tree such that the resulting graph remains acyclic (i.e. a DAG).

We call a node an event and a simple path in the DAG an era. A pair of events \((i,j)\) is plausible if there exists an era (simple path) whose first event is \(i\) and last event is \(j\). Note that the condition \(i < j\) is not necessary to ensure plausibility but in our queries we will only consider pairs with \(i .

Dream then asks you \(Q\) queries. In each query, you are given two integers \(l\) and \(r\) (with \(l \le r\)). Your task is to count the number of plausible pairs of events \((i,j)\) such that \(l \le i ).

Note: The underlying DAG is constructed from the tree edges and the extra \(M\) directed edges. You can assume that the natural order \(1,2,\dots, N\) is a valid topological ordering.

inputFormat

The first line contains three integers \(N\), \(M\), and \(Q\) \( (1 \le N, M, Q \le \text{reasonable limits})\).

The second line contains \(N-1\) integers: \(f_1, f_2, \dots, f_{N-1}\), where \(f_i\) is the parent of node \(i+1\) in the tree.

The next \(M\) lines each contain two integers \(u\) and \(v\) describing an extra directed edge from node \(u\) to node \(v\).

The following \(Q\) lines each contain two integers \(l\) and \(r\) representing a query.

outputFormat

For each query, output a single integer on a new line representing the number of plausible pairs of events \((i,j)\) with \(l \le i < j \le r\) and a path exists from \(i\) to \(j\).

sample

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

10
3
3