题目描述

你需要用一棵树状结构来表示某个方案。数据存储在这棵树的 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, L+1, …, R

并将这些结点染成红色。

你向朋友们征求意见，共收到了 m 条建议。第 j 条建议由两个整数 U_j 和 k_j 给出，表示：

• 对于结点 U_j，至少要有一个它的 k_j 级后代被染成红色。

这些建议彼此独立，且有些建议可能重复。

你希望满足所有朋友的建议，同时让红色结点的数量最少。也就是说，你需要选择一个区间 [L, R]，使得：

• 对每条建议 (U_j, k_j)，区间 [L, R] 中至少包含一个结点，它是 U_j 的 k_j 级后代；
• 区间长度 R - L + 1 最小。

输入格式

第一行输入一个整数 n，表示树的结点数。

第二行输入 n-1 个整数：

p_2, p_3, …, p_n

其中 1 ≤ p_i < i，表示各结点的父亲编号。

第三行输入一个整数 m，表示建议条数。

接下来 m 行，每行两个整数 U_j 和 k_j（1 ≤ U_j < n, 1 ≤ k_j < n），表示一条建议。

保证结点 U_j 至少存在一个 k_j 级后代。

输出格式

输出一行两个整数 L 和 R，表示满足题意的区间 [L, R]。

如果最优解不唯一，输出其中 L 最小 的那一组。

限制

• 2 ≤ n ≤ 200000
• 1 ≤ m ≤ 200000

子任务与评分

只有通过某个子任务中的全部测试，才能获得该子任务的分数。

样例 1

输入

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

输出

3 6

样例 2

输入

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

输出

5 6

样例 1 说明

被染成红色的结点编号为 3, 4, 5, 6。

• 结点 3 是结点 1 的 1 级后代；
• 结点 4 是结点 1 的 2 级后代；
• 结点 6 是结点 3 的 1 级后代。