Die Zusammenarbeit der Mitarbeiter eines Unternehmens ist hierarchisch organisiert. Insgesamt arbeiten $n$ Mitarbeiter im Unternehmen. Jeder Mitarbeiter hat eine eindeutige Nummer von $1$ bis $n$, der Direktor hat die Nummer $1$. Jeder Mitarbeiter außer dem Direktor hat genau einen direkten Vorgesetzten. Der direkte Vorgesetzte von Mitarbeiter $i$ hat die Nummer $p_i$, wobei $p_i<i$ gilt.

Mitarbeiter $x$ ist ein Untergebener der Stufe $1$ von Mitarbeiter $y$, wenn $p_x=y$ gilt. Für $k>1$ ist Mitarbeiter $x$ ein Untergebener der Stufe $k$ von Mitarbeiter $y$, wenn Mitarbeiter $p_x$ ein Untergebener der Stufe $k-1$ von Mitarbeiter $y$ ist.

Der Direktor hat die Möglichkeit, einige Mitarbeiter zu Fortbildungskursen zu schicken. Dazu möchte er zwei Zahlen $L$ und $R$ wählen und alle Mitarbeiter mit Nummern $i$, für die $L\le i\le R$ gilt, zu den Kursen schicken.

Bevor er $L$ und $R$ wählt, hat der Direktor $m$ Wünsche von den Mitarbeitern erhalten. Der $j$-te Wunsch wird durch zwei Zahlen $u_j$ und $k_j$ beschrieben und bedeutet, dass Mitarbeiter $u_j$ darum bittet, einen seiner Untergebenen der Stufe $k_j$ zu den Kursen zu schicken. Um Kosten zu sparen, möchte der Direktor $L$ und $R$ so wählen, dass möglichst wenige Mitarbeiter an der Fortbildung teilnehmen, aber alle Wünsche erfüllt werden.

Schreiben Sie ein Programm, das aus den gegebenen Vorgesetzten-Untergebenen-Beziehungen und den Wünschen der Mitarbeiter solche Zahlen $L$ und $R$ bestimmt, dass durch das Entsenden aller Mitarbeiter mit Nummern von $L$ bis einschließlich $R$ alle Wünsche erfüllt werden und die Anzahl der zur Fortbildung entsandten Mitarbeiter so klein wie möglich ist. Falls es mehrere optimale Zahlenpaare $L,R$ gibt, ist dasjenige mit dem kleinsten Wert von $L$ zu finden.

Eingabe

Die erste Zeile der Eingabedatei enthält die Anzahl $n$ der Mitarbeiter des Unternehmens ($2\le n\le 200\,000$). Die zweite Zeile enthält $n-1$ Zahlen $p_2,p_3,\ldots,p_n$ ($1\le p_i<i$) — die Nummern der direkten Vorgesetzten der Mitarbeiter.

Die dritte Zeile enthält die Anzahl $m$ der Wünsche der Mitarbeiter.

Die folgenden $m$ Zeilen beschreiben die Wünsche der Mitarbeiter und enthalten jeweils zwei ganze Zahlen $u_j,k_j$ ($1\le u_j<n$, $1\le k_j<n$). Es ist garantiert, dass Mitarbeiter $u_j$ mindestens einen Untergebenen der Stufe $k_j$ hat.

Ausgabe

Geben Sie die beiden gesuchten Zahlen $L$ und $R$ aus. Falls es mehrere optimale Paare $(L,R)$ gibt, geben Sie dasjenige mit dem kleinsten Wert von $L$ aus.

Beispiele

Eingabe 1

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

Ausgabe 1

3 6

Hinweis

Die Mitarbeiter mit den Nummern $3$, $4$, $5$ und $6$ werden zur Fortbildung geschickt. Mitarbeiter $3$ ist ein Untergebener der Stufe $1$ von Mitarbeiter $1$, Mitarbeiter $4$ ist ein Untergebener der Stufe $2$ von Mitarbeiter $1$, und Mitarbeiter $6$ ist ein Untergebener der Stufe $1$ von Mitarbeiter $3$.

Teilaufgaben

Die Punkte für eine Teilaufgabe werden nur vergeben, wenn alle Tests dieser Teilaufgabe und der erforderlichen Teilaufgaben bestanden wurden.

Informationen über die Ergebnisse der abschließenden Bewertung

Auf Anfrage werden die Punkte für jede Teilaufgabe mitgeteilt.