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.
| Subtarea | Puntos | Restricciones sobre $n$ | Condiciones adicionales | Subtareas necesarias |
|---|---|---|---|---|
| $1$ | $19$ | $2\le n\le50$ | ||
| $2$ | $25$ | $2\le n\le3000$ | $1$ | |
| $3$ | $21$ | $2\le n\le200\,000$ | Para todo $i$, se cumple $p_i=i-1$ | |
| $4$ | $35$ | $2\le n\le200\,000$ | $1$, $2$, $3$ |
Información sobre los resultados de la evaluación final
Previa solicitud, se comunican los puntos obtenidos en cada subtarea.