Zadanie

Klokany

Počet bodov: 80

Z miestnej ZOO nedávno ušiel párik klokanov a usídlil sa pri neďalekých intrákoch. A keďže študenti mali klokany radi a prikrmovali ich, klokanom sa darilo a začali sa množiť ako besné. Onedlho už okupovali celý les za intrákmi. A tam končila sranda a začínal klokaní teror. Klokanie tlupy čoraz častejšie vyrážali z lesa na lúpežné výjazdy, pri ktorých devastovali záhradky, prevracali smetné koše a prehrýzali káble všetkého druhu.

Pod lesom sídli istá nemenovaná softvérová firma. Aj tej už klokanie nájazdy pekne strpčujú život, a tak jedného dňa šéf rozhodol, že sa niektorí zamestnanci musia ísť zúčastniť školenia na boj proti divým klokanom.

Lenže každý z týchto zamestnancov má tisíc roboty na meškajúcich zákazkách a updatoch, a tak niet divu, že táto lukratívna ponuka putovala rovno ich podriadeným.

Firma má stromovú hierarchiu. Vo firme je \(n\) ľudí, očíslovaných od 1 po \(n\). Číslo 1 má riaditeľ. Pre každé \(i > 1\) má človek \(i\) jedného priameho nadriadeného \(p_i\), pričom platí, že \(p_i < i\).

Všimnime si ľubovoľného zamestnanca \(Z\). Jeho priamych podriadených budeme volať podriadení prvej úrovne. Ich priami podriadení sú z pohľadu zamestnanca \(Z\) podriadenými druhej úrovne, a tak ďalej.

Na vstupe je zoznam informácií nasledujúceho tvaru: zamestnanec \(z_i\) rozhodol, že aspoň jeden z jeho podriadených \(u_i\)-tej úrovne musí ísť na školenie proti klokanom.

Treba rozhodnúť, kto všetko pôjde na školenie, a to tak, aby celkový počet vyškolených ľudí bol najmenší možný.

Aby to nebolo také ľahké, je tu ešte jeden háčik: riaditeľ neodsúhlasí žiaden príliš komplikovaný návrh. Jediné, čo má šancu na úspech, sú návrhy typu nech idú na školenie zamestnanci, ktorých čísla sú od \(a\) po \(b\) vrátane.

Vstup a výstup

V prvom riadku vstupu je počet zamestnancov: celé číslo \(n\).

V prvej sade platí \(2 \leq n \leq 3000\). V druhej sade platí \(2 \leq n \leq 200\,000\).

V druhom riadku je \(n - 1\) čísel: čísla \(p_2\) až \(p_n\). Pripomíname, že vždy platí \(1 \leq p_i < i\).

V treťom riadku je číslo \(m\): počet informácií o tom, kto chce koho poslať na školenie. Platí \(1 \leq m \leq 200\,000\).

Nasleduje \(m\) riadkov, v každom z nich sú čísla \(z_i\) a \(u_i\) popisujúce jednu informáciu. Vždy platí \(1 \leq z_i < n\), \(1 \leq u_i < n\) a navyše vždy platí, že zamestnanec \(z_i\) naozaj má aspoň jedného podriadeného \(u_i\)-tej úrovne.

Vypíšte jeden riadok a v ňom dve medzerou oddelené celé čísla \(a\), \(b\) udávajúce interval zamestnancov, ktorých treba poslať na školenie. Tento interval musí spĺňať všetky požiadavky zo vstupu. Ak existuje viacero možností, nájdite a vypíšte tú, v ktorej je počet zamestnancov na školení najmenší možný. Ak stále existuje viacero možností, vypíšte tú s najmenším \(a\).

Príklady

Input:

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

Output:

3 6

Na školenie pôjdu zamestnanci s číslami od 3 do 6. Prvá požiadavka bola, že tam má byť priamy podriadený zamestnanca 1. Toto je splnené: je ním zamestnanec 3. Druhá požiadavka bola, že tam má byť priamy podriadený zamestnanca 3. Aj toto je splnené, zamestnanec 6 patrí medzi priamych podriadených zamestnanca 3. No a posledná požiadavka bola, že na školení má byť aspoň jeden podriadený druhej úrovne pod zamestnancom 1. Toto mohol byť hocikto zo zamestnancov 4, 5, 6, 7, a skutočne tam aspoň jeden z nich je. Všetko je teda v poriadku. A ľahko nahliadneme, že žiaden kratší vyhovujúci interval neexistuje.