题目背景

翻译自 ROIR 2017 D2T4。

题目描述

某公司共有 $n$ 名员工，每个员工都有一个唯一的编号，编号从 $1$ 到 $n$。编号为 $1$ 的员工是公司总经理，除了总经理之外，每个员工都有一个直接上级，员工 $i$ 的直接上级编号为 $p_i$，且有 $p_i < i$。

若 $p_x = y$，则员工 $x$ 被称为员工 $y$ 的第 $1$ 层下属；若员工 $p_x$ 是员工 $y$ 的第 $k-1$ 层下属，则员工 $x$ 被称为员工 $y$ 的第 $k$ 层下属。

现在，公司总经理可以选择一些员工参加培训。他决定选择两个数字 $L$ 和 $R$，将所有编号满足 $L \leq i \leq R$ 的员工送去培训。

在确定 $L$ 和 $R$ 之前，总经理收到了 $m$ 条员工的要求，第 $j$ 条要求用两个数字 $u_j$ 和 $k_j$ 表示，这代表员工 $u_j$ 希望其第 $k_j$ 层下属中至少有一个被送去培训。为了节省费用，总经理希望确定 $L$ 和 $R$ 的值使得送去培训的员工人数最少，并且所有员工的要求都能满足。

需要编写程序，根据公司内部的上下级关系和员工的要求，找出一对 $L$ 和 $R$，使得所有要求都能得到满足，并且送去培训的员工人数最少。如果有多个满足条件的 $(L, R)$ 对，选择其中 $L$ 最小的那个。

输入格式

第一行输入一个整数 $n$，表示公司员工的总数（$2 \leq n \leq 200000$）。

第二行输入 $n-1$ 个整数 $p_2, p_3, \dots, p_n$，其中 $p_i$ 表示员工 $i$ 的直接上级编号，且 $1 \leq p_i < i$。

第三行输入一个整数 $m$，表示员工的要求数量。

接下来 $m$ 行，每行包含两个整数 $u_j$ 和 $k_j$，表示第 $j$ 条要求。

输出格式

输出两个整数 $L$ 和 $R$，表示选择的员工编号区间。如果存在多个符合条件的 $(L, R)$ 对，输出其中 $L$ 最小的那一对。

7
1 1 2 2 3 3
3
1 1
3 1
1 2

3 6

提示

样例解释

员工编号为 $3,4,5,6$ 的员工将被送去培训。这满足所有要求，因为员工 $3$ 是员工 $1$ 的第 $1$ 层下属，员工 $4$ 是员工 $1$ 的第 $2$ 层下属，员工 $6$ 是员工 $3$ 的第 $1$ 层下属。

数据范围