A interação entre os funcionários de uma empresa é organizada numa estrutura hierárquica. A empresa tem, ao todo, $n$ funcionários. Cada funcionário recebe um número único de $1$ a $n$, e o diretor recebe o número $1$. Cada funcionário, exceto o diretor, tem exatamente um superior imediato. O superior imediato do funcionário $i$ tem o número $p_i$, com $p_i<i$.

O funcionário $x$ é um subordinado de nível $1$ do funcionário $y$ se $p_x=y$. Para $k>1$, o funcionário $x$ é um subordinado de nível $k$ do funcionário $y$ se o funcionário $p_x$ for um subordinado de nível $k-1$ do funcionário $y$.

O diretor da empresa tem a oportunidade de enviar alguns funcionários para cursos de aperfeiçoamento profissional. Para isso, decidiu escolher dois números $L$ e $R$ e enviar para os cursos todos os funcionários cujos números $i$ satisfazem $L\le i\le R$.

Antes de escolher $L$ e $R$, o diretor recebeu $m$ pedidos dos funcionários da empresa. O pedido de número $j$ é definido por dois números $u_j$ e $k_j$ e significa que o funcionário $u_j$ pede que um dos seus subordinados de nível $k_j$ seja enviado para os cursos. Para economizar recursos, o diretor quer escolher $L$ e $R$ de modo a minimizar o número de funcionários enviados para o aperfeiçoamento, mas atendendo a todos os pedidos.

Escreva um programa que, dadas as relações entre superiores e subordinados na empresa e os pedidos dos funcionários, determine números $L$ e $R$ tais que, ao enviar todos os funcionários com números de $L$ a $R$, inclusive, para os cursos de aperfeiçoamento, todos os pedidos sejam atendidos e o número de funcionários enviados seja o menor possível. Se houver vários pares ótimos $L,R$, deve ser encontrado aquele cujo valor de $L$ é o menor.

Entrada

A primeira linha do arquivo de entrada contém o número $n$ — a quantidade de funcionários da empresa ($2\le n\le200\,000$). A segunda linha contém $n-1$ números: $p_2,p_3,\ldots,p_n$ ($1\le p_i<i$) — os números dos superiores imediatos dos funcionários.

A terceira linha contém o número $m$ — a quantidade de pedidos dos funcionários.

As $m$ linhas seguintes definem os pedidos e contêm, cada uma, dois números inteiros $u_j,k_j$ ($1\le u_j<n$, $1\le k_j<n$; é garantido que o funcionário $u_j$ tem pelo menos um subordinado de nível $k_j$).

Saída

Imprima os dois números procurados: $L$ e $R$. Se houver vários pares ótimos $(L,R)$, imprima aquele com o menor valor de $L$.

Exemplos

Entrada 1

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

Saída 1

3 6

Nota

Os funcionários com números $3$, $4$, $5$ e $6$ serão enviados para o aperfeiçoamento. O funcionário número $3$ é subordinado de nível $1$ do funcionário número $1$, o funcionário número $4$ é subordinado de nível $2$ do funcionário número $1$, e o funcionário número $6$ é subordinado de nível $1$ do funcionário número $3$.

Subtarefas

Os pontos de cada subtarefa só são concedidos se todos os testes dessa subtarefa e das subtarefas necessárias forem superados com sucesso.

Obtenção de informações sobre os resultados da avaliação final

Mediante solicitação, são informados os pontos de cada subtarefa.