연수 대상 구간 선정

이 회사의 직원들은 계층 구조를 이룹니다. 회사에는 $n$명의 직원이 있으며, 1부터 $n$까지 번호가 붙어 있습니다. 사장의 번호는 1입니다. 사장을 제외한 모든 직원에게는 직속 상사가 정확히 한 명 있습니다. 직원 $i$의 직속 상사 번호는 $p_i$이며, $p_i < i$입니다.

$p_x = y$이면 직원 $x$는 직원 $y$의 레벨 1 부하 직원입니다. $k > 1$일 때 $p_x$가 직원 $y$의 레벨 $k-1$ 부하 직원이면, 직원 $x$는 직원 $y$의 레벨 $k$ 부하 직원입니다.

사장은 일부 직원을 연수 과정에 보내려 합니다. 두 수 $L$과 $R$을 고르고, $L \le i \le R$을 만족하는 모든 직원 $i$를 연수에 보냅니다.

$L$과 $R$을 고르기 전에 사장은 직원들로부터 $m$개의 요청을 받았습니다. $j$번째 요청은 두 수 $u_j$, $k_j$로 주어지며, 직원 $u_j$가 자신의 레벨 $k_j$ 부하 직원 한 명을 연수에 보내 달라는 뜻입니다. 사장은 비용을 줄이기 위해 모든 요청을 만족하면서 연수에 가는 직원 수가 가장 적도록 $L$과 $R$을 고릅니다. 최적의 쌍이 여러 개이면 $L$이 가장 작은 쌍을 택합니다.

첫 줄에는 직원 수 $n$이 주어집니다 ($2 \le n \le 200000$). 둘째 줄에는 $n-1$개의 정수 $p_2, p_3, \ldots, p_n$ ($1 \le p_i < i$)이 주어지며, 각각 직원 $i$의 직속 상사 번호입니다. 셋째 줄에는 요청 수 $m$이 주어집니다. 이어지는 $m$개의 줄에는 두 정수 $u_j$, $k_j$ ($1 \le u_j < n$, $1 \le k_j < n$)가 주어집니다. 직원 $u_j$에게는 레벨 $k_j$ 부하 직원이 적어도 한 명 있음이 보장됩니다.

두 정수 $L$과 $R$을 출력합니다. 최적의 쌍 $(L, R)$이 여러 개이면 $L$이 가장 작은 쌍을 출력합니다.

연수에 보내지는 직원은 3, 4, 5, 6번입니다. 직원 3은 사장 1의 레벨 1 부하 직원입니다. 직원 4는 사장 1의 레벨 2 부하 직원입니다. 직원 6은 직원 3의 레벨 1 부하 직원입니다.