题目描述

译自 ROIR 2017 Day2 T4. Повышение квалификации

某公司的员工互动以层级结构组织。公司共有 $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 \leq i \leq R$ 范围内的所有员工送往培训。

在选择 $L$ 和 $R$ 之前，总监收到了公司员工的 $m$ 个请求。第 $j$ 个请求由两个数字 $u_j$ 和 $k_j$ 组成，表示员工 $u_j$ 请求将他的某个 $k_j$ 级下属送往培训。为了节约成本，总监希望选择 $L$ 和 $R$，使得送往培训的员工数量最少，但同时满足所有请求。

你的任务是编写一个程序，根据公司上下级关系和员工请求，确定数字 $L$ 和 $R$，使得将编号从 $L$ 到 $R$（含两端）的所有员工送往培训时，所有请求都被满足，且送往培训的员工数量最少。如果存在多个最优的 $L, R$ 对，需要找到 $L$ 值最小的解。

输入格式

输入文件的第一行包含一个整数 $n$ $(2 \leq n \leq 200000)$，表示公司员工数量。

第二行包含 $(n-1)$ 个整数 $p_2, p_3, \ldots, p_n$ $(1 \leq p_i < i)$，表示员工的直接上级编号。

第三行包含一个整数 $m$，表示员工请求的数量。

接下来的 $m$ 行描述员工请求，每行包含两个整数 $u_j, k_j$（$1 \leq u_j < n$，$1 \leq k_j < n$，保证员工 $u_j$ 至少有一个 $k_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$ 级下属。

数据范围与提示

详细子任务附加限制及分值如下表所示：