ある会社の従業員間の関係は階層構造になっています。会社には $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$ を選び、番号 $i$ が $L \le i \le R$ を満たす従業員全員を研修に参加させることにしました。

$L$ と $R$ を選ぶ前に、社長は従業員から $m$ 個の希望を受け取りました。$j$ 番目の希望は二つの数 $u_j$ と $k_j$ で与えられ、従業員 $u_j$ が自分のレベル $k_j$ の部下の一人を研修に参加させてほしいという意味です。費用を節約するため、社長はすべての希望を満たしながら、研修に参加させる従業員数ができるだけ少なくなるように $L$ と $R$ を選びたいと考えています。

会社の上司と部下の関係および従業員の希望が与えられたとき、番号 $L$ から $R$ までの従業員全員を研修に参加させればすべての希望が満たされ、参加人数が最小となる $L$ と $R$ を求めるプログラムを書いてください。両端も含みます。最適な組 $L,R$ が複数ある場合は、$L$ が最小の組を求めてください。

入力

入力ファイルの 1 行目には従業員数 $n$ が含まれます（$2 \le n \le 200\,000$）。2 行目には、従業員の直属の上司の番号を表す $n-1$ 個の数 $p_2,p_3,\ldots,p_n$ が含まれます（$1 \le p_i<i$）。

3 行目には従業員の希望の個数 $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$ が最小の組を出力してください。

入出力例

入力 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$ の部下です。

小課題

各小課題の得点は、その小課題と必要な小課題のすべてのテストに合格した場合にのみ与えられます。

最終採点結果の情報

要求に応じて、各小課題の得点が通知されます。