Minimizing Training Segment with Subordinate Requirements

A company has \(n\) employees numbered from \(1\) to \(n\). Employee \(1\) is the general manager. For each employee \(i\) (\(2 \leq i \leq n\)), there is a direct supervisor with index \(p_i\) (and \(p_i < i\)).

We define the subordinate levels as follows: if \(p_x = y\) then employee \(x\) is a 1st-level subordinate of employee \(y\). Moreover, if employee \(x\)'s direct supervisor \(p_x\) is a \( (k-1)\)-th level subordinate of employee \(y\), then employee \(x\) is a \(k\)-th level subordinate of employee \(y\).

The general manager intends to send a group of employees to training. He chooses two numbers \(L\) and \(R\) and sends all employees whose numbers satisfy \(L \leq i \leq R\) to training.

Before finalizing \(L\) and \(R\), he has received \(m\) requests. The \(j\)-th request is given by two numbers \(u_j\) and \(k_j\). This means that employee \(u_j\) requires that at least one of his \(k_j\)-th level subordinates be sent to training.

The objective is to determine a pair \((L, R)\) such that all requests are satisfied while minimizing the total number of employees sent to training (i.e. minimizing \(R-L+1\)). If there are multiple solutions, choose the one with the smallest \(L\).

Note: All formulas are written in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(m\) --- the number of employees and the number of requests.

The second line contains \(n-1\) integers: \(p_2, p_3, \ldots, p_n\) where \(p_i\) is the direct supervisor of employee \(i\) (\(1 \leq p_i < i\)).

Each of the next \(m\) lines contains two integers \(u_j\) and \(k_j\) representing a request from employee \(u_j\) that at least one of his \(k_j\)-th level subordinates is sent for training.

outputFormat

Output two integers \(L\) and \(R\) representing the chosen contiguous range such that all requests are satisfied and the total number of employees sent (i.e. \(R-L+1\)) is minimized. If there are multiple best answers, choose the one with the smallest \(L\).

sample

5 2
1 1 2 2
1 1
2 1

3 4