Training Selection

The employees of a company form a hierarchy. The company has $n$ employees, numbered from 1 to $n$. The director has number 1. Every employee except the director has exactly one direct supervisor. The direct supervisor of employee $i$ has number $p_i$, and $p_i < i$.

Employee $x$ is a subordinate of level 1 of employee $y$ if $p_x = y$. For $k > 1$, employee $x$ is a subordinate of level $k$ of employee $y$ if employee $p_x$ is a subordinate of level $k-1$ of employee $y$.

The director wants to send some employees to a training course. He chooses two numbers $L$ and $R$ and sends every employee $i$ with $L \le i \le R$.

Before choosing $L$ and $R$, the director received $m$ requests. The $j$-th request is a pair $u_j$, $k_j$ and means that employee $u_j$ asks to send one of their subordinates of level $k_j$ to the course. To save money, the director wants the number of employees sent to the course to be as small as possible, while all requests are fulfilled. If several pairs $(L, R)$ are optimal, he chooses the one with the smallest $L$.

The first line contains $n$, the number of employees ($2 \le n \le 200000$). The second line contains $n-1$ integers $p_2, p_3, \ldots, p_n$ ($1 \le p_i < i$), the direct supervisor of each employee $i$. The third line contains $m$, the number of requests. Each of the next $m$ lines contains two integers $u_j$ and $k_j$ ($1 \le u_j < n$, $1 \le k_j < n$). It is guaranteed that employee $u_j$ has at least one subordinate of level $k_j$.

Print two integers $L$ and $R$. If several pairs $(L, R)$ are optimal, print the pair with the smallest $L$.

Employees 3, 4, 5, and 6 are sent to the course. Employee 3 is a subordinate of level 1 of employee 1. Employee 4 is a subordinate of level 2 of employee 1. Employee 6 is a subordinate of level 1 of employee 3.