I rapporti tra i dipendenti di un’azienda sono organizzati in una struttura gerarchica. L’azienda ha $n$ dipendenti. Ogni dipendente ha un numero univoco da $1$ a $n$, e il direttore ha il numero $1$. Ogni dipendente, tranne il direttore, ha esattamente un superiore diretto. Il superiore diretto del dipendente $i$ ha numero $p_i$, con $p_i<i$.

Il dipendente $x$ è un subordinato di livello $1$ del dipendente $y$ se $p_x=y$. Per $k>1$, il dipendente $x$ è un subordinato di livello $k$ del dipendente $y$ se il dipendente $p_x$ è un subordinato di livello $k-1$ del dipendente $y$.

Il direttore ha l’opportunità di mandare alcuni dipendenti a corsi di perfezionamento professionale. Ha quindi deciso di scegliere due numeri $L$ e $R$ e mandare ai corsi tutti i dipendenti con numeri $i$ tali che $L \le i \le R$.

Prima di scegliere $L$ e $R$, il direttore ha ricevuto $m$ richieste dai dipendenti. La richiesta numero $j$ è specificata da due numeri $u_j$ e $k_j$ e significa che il dipendente $u_j$ chiede di mandare ai corsi uno dei suoi subordinati di livello $k_j$. Per risparmiare, il direttore vuole scegliere $L$ e $R$ in modo che il numero di dipendenti mandati ai corsi sia il minimo possibile e tutte le richieste siano soddisfatte.

Scrivi un programma che, dati i rapporti superiore-subordinato e le richieste dei dipendenti, trovi $L$ e $R$ tali che mandando ai corsi tutti i dipendenti con numeri da $L$ a $R$, estremi inclusi, siano soddisfatte tutte le richieste e il numero di dipendenti mandati sia minimo. Se ci sono più coppie ottimali $L,R$, trova quella con $L$ minimo.

Input

La prima riga del file di input contiene il numero $n$ di dipendenti ($2 \le n \le 200\,000$). La seconda riga contiene $n-1$ numeri $p_2,p_3,\ldots,p_n$ ($1 \le p_i<i$), i numeri dei superiori diretti dei dipendenti.

La terza riga contiene $m$, il numero di richieste dei dipendenti.

Le successive $m$ righe descrivono le richieste e contengono ciascuna due interi $u_j,k_j$ ($1 \le u_j<n$, $1 \le k_j<n$; è garantito che il dipendente $u_j$ abbia almeno un subordinato di livello $k_j$).

Output

Stampa i due numeri cercati, $L$ e $R$. Se ci sono più coppie ottimali $(L,R)$, stampa quella con $L$ minimo.

Esempi

Input 1

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

Output 1

3 6

Nota

Vengono mandati ai corsi i dipendenti con numeri $3$, $4$, $5$ e $6$. Il dipendente $3$ è subordinato di livello $1$ del dipendente $1$, il dipendente $4$ è subordinato di livello $2$ del dipendente $1$, e il dipendente $6$ è subordinato di livello $1$ del dipendente $3$.

Sottoproblemi

I punti di ciascun sottoproblema sono assegnati solo se tutti i test di quel sottoproblema e dei sottoproblemi necessari vengono superati.

Informazioni sui risultati della valutazione finale

Su richiesta viene comunicato il punteggio di ciascun sottoproblema.