Relacje między pracownikami pewnej firmy mają strukturę hierarchiczną. W firmie pracuje łącznie $n$ osób. Każdy pracownik ma unikalny numer od $1$ do $n$, a dyrektor ma numer $1$. Każdy pracownik oprócz dyrektora ma dokładnie jednego bezpośredniego przełożonego. Bezpośredni przełożony pracownika $i$ ma numer $p_i$, przy czym $p_i<i$.

Pracownik $x$ jest podwładnym poziomu $1$ pracownika $y$, jeśli $p_x=y$. Dla $k>1$ pracownik $x$ jest podwładnym poziomu $k$ pracownika $y$, jeśli pracownik $p_x$ jest podwładnym poziomu $k-1$ pracownika $y$.

Dyrektor firmy otrzymał możliwość skierowania niektórych pracowników na kursy podnoszenia kwalifikacji. Postanowił w tym celu wybrać dwie liczby $L$ i $R$ oraz skierować na kursy wszystkich pracowników o numerach $i$ spełniających $L\le i\le R$.

Przed wyborem liczb $L$ i $R$ dyrektor otrzymał $m$ życzeń od pracowników firmy. Życzenie $j$ jest opisane dwiema liczbami $u_j$ i $k_j$ i oznacza, że pracownik $u_j$ prosi o skierowanie na kursy jednego ze swoich podwładnych poziomu $k_j$. Aby zaoszczędzić środki, dyrektor chce wybrać takie $L$ i $R$, by liczba skierowanych pracowników była jak najmniejsza, a zarazem wszystkie życzenia zostały spełnione.

Napisz program, który na podstawie relacji przełożony–podwładny w firmie i życzeń pracowników wyznaczy takie liczby $L$ i $R$, że skierowanie na kursy wszystkich pracowników o numerach od $L$ do $R$ włącznie spełni wszystkie życzenia i zminimalizuje liczbę skierowanych pracowników. Jeśli istnieje kilka optymalnych par liczb $L,R$, należy znaleźć tę, w której $L$ jest najmniejsze.

Wejście

Pierwszy wiersz pliku wejściowego zawiera liczbę $n$, czyli liczbę pracowników firmy ($2\le n\le 200\,000$). Drugi wiersz zawiera $n-1$ liczb $p_2,p_3,\ldots,p_n$ ($1\le p_i<i$), czyli numery bezpośrednich przełożonych pracowników.

Trzeci wiersz zawiera liczbę $m$, czyli liczbę życzeń pracowników.

Kolejne $m$ wierszy opisuje życzenia pracowników. Każdy zawiera dwie liczby całkowite $u_j,k_j$ ($1\le u_j<n$, $1\le k_j<n$; gwarantuje się, że pracownik $u_j$ ma co najmniej jednego podwładnego poziomu $k_j$).

Wyjście

Wypisz dwie poszukiwane liczby: $L$ i $R$. Jeśli istnieje kilka optymalnych par $(L,R)$, wypisz tę, w której $L$ jest najmniejsze.

Przykład

Wejście 1

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

Wyjście 1

3 6

Uwagi

Na kursy zostaną skierowani pracownicy o numerach $3$, $4$, $5$ i $6$. Pracownik $3$ jest podwładnym poziomu $1$ pracownika $1$, pracownik $4$ jest podwładnym poziomu $2$ pracownika $1$, a pracownik $6$ jest podwładnym poziomu $1$ pracownika $3$.

Podzadania

Punkty za każde podzadanie przyznaje się wyłącznie po zaliczeniu wszystkich testów tego podzadania oraz wymaganych podzadań.

Informacje o wynikach końcowego sprawdzania

Na żądanie udostępniane są punkty za każde podzadanie.