تُنظَّم العلاقات بين موظفي شركة في بنية هرمية. تضم الشركة $n$ موظفًا. يُمنح كل موظف رقمًا فريدًا من $1$ إلى $n$، ويحمل المدير الرقم $1$. لكل موظف، باستثناء المدير، رئيس مباشر واحد بالضبط. رقم الرئيس المباشر للموظف $i$ هو $p_i$، حيث $p_i<i$.

يكون الموظف $x$ مرؤوسًا من المستوى $1$ للموظف $y$ إذا كان $p_x=y$. ولـ$k>1$، يكون الموظف $x$ مرؤوسًا من المستوى $k$ للموظف $y$ إذا كان الموظف $p_x$ مرؤوسًا من المستوى $k-1$ للموظف $y$.

أُتيحت لمدير الشركة فرصة إرسال بعض الموظفين إلى دورات تطوير مهني. لذلك قرر اختيار عددين $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$ أصغر ما يمكن.

الإدخال

يحتوي السطر الأول من ملف الإدخال على عدد الموظفين $n$ ($2 \le n \le 200\,000$). يحتوي السطر الثاني على $n-1$ عدد $p_2,p_3,\ldots,p_n$ ($1 \le p_i<i$)، وهي أرقام الرؤساء المباشرين للموظفين.

يحتوي السطر الثالث على $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$ مرؤوس من المستوى $2$ للموظف $1$، والموظف $6$ مرؤوس من المستوى $1$ للموظف $3$.

المهام الفرعية

لا تُمنح نقاط مهمة فرعية إلا إذا اجتازت جميع اختبارات تلك المهمة والمهام الفرعية المطلوبة.

معلومات عن نتائج التقييم النهائي

تُقدَّم نقاط كل مهمة فرعية عند الطلب.