La interacción entre los empleados de una empresa está organizada mediante una estructura jerárquica. En total, la empresa tiene $n$ empleados. A cada empleado se le asigna un número único de $1$ a $n$; el director tiene el número $1$. Cada empleado, salvo el director, tiene exactamente un jefe inmediato. El jefe inmediato del empleado $i$ tiene el número $p_i$, y se cumple $p_i<i$.

El empleado $x$ es un subordinado de nivel $1$ del empleado $y$ si $p_x=y$. Para $k>1$, el empleado $x$ es un subordinado de nivel $k$ del empleado $y$ si el empleado $p_x$ es un subordinado de nivel $k-1$ del empleado $y$.

El director de la empresa tiene la posibilidad de enviar a algunos empleados a cursos de formación profesional. Para ello, ha decidido elegir dos números $L$ y $R$ y enviar a los cursos a todos los empleados con números $i$ tales que $L\le i\le R$.

Antes de elegir $L$ y $R$, el director recibió $m$ peticiones de los empleados de la empresa. La petición $j$ se define mediante dos números $u_j$ y $k_j$, y significa que el empleado $u_j$ pide que se envíe a los cursos a uno de sus subordinados de nivel $k_j$. Para ahorrar dinero, el director quiere elegir $L$ y $R$ de modo que el número de empleados enviados a los cursos sea el mínimo posible y se cumplan todas las peticiones.

Debes escribir un programa que, dadas las relaciones entre jefes y subordinados de la empresa y las peticiones de los empleados, determine los números $L$ y $R$ tales que, al enviar a los cursos a todos los empleados con números de $L$ a $R$, ambos inclusive, se cumplan todas las peticiones y el número de empleados enviados sea el mínimo posible. Si hay varios pares óptimos de números $L,R$, debes encontrar aquel cuyo valor de $L$ sea mínimo.

Entrada

La primera línea contiene el número $n$, la cantidad de empleados de la empresa ($2\le n\le200\,000$). La segunda línea contiene $n-1$ números $p_2,p_3,\ldots,p_n$ ($1\le p_i<i$), los números de los jefes inmediatos de los empleados.

La tercera línea contiene el número $m$, la cantidad de peticiones de los empleados.

Las siguientes $m$ líneas describen las peticiones y contienen dos enteros $u_j,k_j$ cada una ($1\le u_j<n$, $1\le k_j<n$; se garantiza que el empleado $u_j$ tiene al menos un subordinado de nivel $k_j$).

Salida

Imprime los dos números buscados: $L$ y $R$. Si hay varios pares óptimos $(L,R)$, imprime aquel cuyo valor de $L$ sea mínimo.

Ejemplos

Entrada 1

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

Salida 1

3 6

Nota

Se enviará a los cursos a los empleados con números $3$, $4$, $5$ y $6$. El empleado $3$ es un subordinado de nivel $1$ del empleado $1$; el empleado $4$ es un subordinado de nivel $2$ del empleado $1$; y el empleado $6$ es un subordinado de nivel $1$ del empleado $3$.

Subtareas

Los puntos de cada subtarea se otorgan únicamente si se superan todos los tests de esa subtarea y de las subtareas necesarias.

Información sobre los resultados de la evaluación final

Previa solicitud, se comunican los puntos obtenidos en cada subtarea.