Les relations entre les employés d'une entreprise sont organisées selon une structure hiérarchique. L'entreprise compte $n$ employés. Chaque employé possède un numéro unique de $1$ à $n$, le directeur portant le numéro $1$. Chaque employé, à l'exception du directeur, a exactement un supérieur direct. Le supérieur direct de l'employé $i$ porte le numéro $p_i$, avec $p_i<i$.

L'employé $x$ est un subordonné de niveau $1$ de l'employé $y$ si $p_x=y$. Pour $k>1$, l'employé $x$ est un subordonné de niveau $k$ de l'employé $y$ si l'employé $p_x$ est un subordonné de niveau $k-1$ de l'employé $y$.

Le directeur de l'entreprise a la possibilité d'envoyer certains employés suivre des cours de perfectionnement. Il a décidé pour cela de choisir deux nombres $L$ et $R$ et d'envoyer en formation tous les employés dont le numéro $i$ vérifie $L\le i\le R$.

Avant de choisir les nombres $L$ et $R$, le directeur a reçu $m$ souhaits des employés de l'entreprise. Le $j$-ième souhait est donné par deux nombres $u_j$ et $k_j$ et signifie que l'employé $u_j$ demande d'envoyer en formation l'un de ses subordonnés de niveau $k_j$. Pour économiser de l'argent, le directeur souhaite choisir $L$ et $R$ de sorte que le nombre d'employés envoyés en formation soit aussi petit que possible, tout en satisfaisant tous les souhaits.

Écrivez un programme qui, à partir des relations supérieur-subordonné de l'entreprise et des souhaits des employés, détermine deux nombres $L$ et $R$ tels qu'envoyer en formation tous les employés portant les numéros de $L$ à $R$ inclus satisfasse tous les souhaits et minimise le nombre d'employés envoyés. S'il existe plusieurs paires optimales $L,R$, trouvez celle dont la valeur de $L$ est minimale.

Entrée

La première ligne du fichier d'entrée contient le nombre $n$ d'employés de l'entreprise ($2\le n\le200\,000$). La deuxième ligne contient $n-1$ nombres : $p_2,p_3,\ldots,p_n$ ($1\le p_i<i$), les numéros des supérieurs directs des employés.

La troisième ligne contient le nombre $m$ de souhaits des employés.

Les $m$ lignes suivantes décrivent les souhaits des employés et contiennent chacune deux entiers $u_j,k_j$ ($1\le u_j<n$, $1\le k_j<n$). Il est garanti que l'employé $u_j$ possède au moins un subordonné de niveau $k_j$.

Sortie

Affichez les deux nombres recherchés, $L$ et $R$. S'il existe plusieurs paires optimales $(L,R)$, affichez celle dont la valeur de $L$ est minimale.

Exemples

Entrée 1

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

Sortie 1

3 6

Remarque

Les employés portant les numéros $3$, $4$, $5$ et $6$ seront envoyés en formation. L'employé numéro $3$ est un subordonné de niveau $1$ de l'employé numéro $1$, l'employé numéro $4$ est un subordonné de niveau $2$ de l'employé numéro $1$, et l'employé numéro $6$ est un subordonné de niveau $1$ de l'employé numéro $3$.

Sous-tâches

Les points d'une sous-tâche sont attribués uniquement si tous les tests de cette sous-tâche et des sous-tâches nécessaires sont réussis.

Obtention des informations sur les résultats de l'évaluation finale

Sur demande, les points de chaque sous-tâche sont communiqués.