题目描述

某池塘共有 $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$ 最小的那一对。

输入输出样例 #1

输入 #1

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

输出 #1

3 6

说明/提示

样例解释

青蛙编号为 $3,4,5,6$ 的青蛙将被送去火锅。这满足所有要求，因为青蛙 $3$ 是青蛙 $1$ 的第 $1$ 层蝌蚪，青蛙 $4$ 是青蛙 $1$ 的第 $2$ 层蝌蚪，青蛙 $6$ 是青蛙 $3$ 的第 $1$ 层蝌蚪。

数据范围