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.
| Subtarefa | Pontos | Restrições: $n$ | Condições adicionais | Subtarefas necessárias |
|---|---|---|---|---|
| $1$ | $19$ | $2\le n\le50$ | ||
| $2$ | $25$ | $2\le n\le3000$ | $1$ | |
| $3$ | $21$ | $2\le n\le200\,000$ | Para todo $i$, $p_i=i-1$ | |
| $4$ | $35$ | $2\le n\le200\,000$ | $1,2,3$ |
Obtenção de informações sobre os resultados da avaliação final
Mediante solicitação, são informados os pontos de cada subtarefa.