En una corporación trabajan $n$ empleados, uno de los cuales es el director. Cada empleado, salvo el director, tiene exactamente un superior directo.

Cada empleado realiza un trabajo estrictamente determinado. Si el empleado $a$ necesita que se realice el trabajo del empleado $b$, debe enviarle una solicitud. Según la política de la corporación, una solicitud solo puede transmitirse directamente de un empleado a su superior directo o, en sentido contrario, de un superior a un subordinado directo. La solicitud pasa de un empleado a otro hasta llegar al empleado $b$.

Para reducir la carga de los empleados, la corporación ha contratado a $k$ mensajeros. El mensajero $i$ está asignado a la pareja de empleados $a_i$ y $b_i$, y entrega solicitudes entre ellos. Si uno de los empleados de esta pareja necesita enviar una solicitud al otro, se la entrega al mensajero, que la transmite sucesivamente entre empleados según la política de la corporación, hasta que haya pasado por todos los empleados intermedios necesarios y llegue al destinatario. Al entregar una solicitud, el mensajero no visita al mismo empleado más de una vez.

Para optimizar los gastos, se ha decidido encontrar dos mensajeros cuyos recorridos se solapen lo más posible, prescindir de uno de ellos y encargar su trabajo al otro. Llamaremos grado de duplicación de una pareja de mensajeros al número de pasos entre un empleado y su superior directo, en cualquiera de los dos sentidos, que pertenecen tanto al recorrido del primer mensajero como al del segundo.

Escribe un programa que encuentre dos mensajeros con el mayor grado de duplicación.

Entrada

La primera línea contiene dos enteros: $n$, el número de empleados, y $k$, el número de mensajeros ($2\le n,k\le 2\cdot 10^5$). Los empleados están numerados de $1$ a $n$, y el director tiene el número $1$.

La segunda línea contiene $n-1$ enteros $p_2,p_3,\ldots,p_n$, los números de los superiores directos de todos los empleados salvo el director ($1\le p_i<i$).

Las siguientes $k$ líneas contienen dos enteros $a_i$ y $b_i$, los números de los empleados de la pareja asignada al mensajero $i$ ($1\le a_i,b_i\le n$; $a_i\ne b_i$). Puede haber varios mensajeros asignados a la misma pareja de empleados.

Salida

La primera línea debe contener un único entero: el mayor grado de duplicación de dos mensajeros.

La segunda línea debe contener dos enteros distintos entre $1$ y $k$: los números de los mensajeros de una pareja con el mayor grado de duplicación. Si hay varias parejas así, puedes imprimir cualquiera de ellas.

Nota

Diremos que el empleado $a$ obedece las órdenes del empleado $b$ si $b$ es el superior directo de $a$, o si el superior directo de $a$ obedece las órdenes de $b$. Es natural llamar importante a un mensajero que transmite solicitudes de un empleado a alguien que obedece sus órdenes, o en sentido contrario.

Subtareas

Ejemplos

Entrada 1

4 2
1 2 2
1 3
1 4

Salida 1

1
2 1

Entrada 2

4 2
1 2 3
1 2
3 4

Salida 2

0
1 2

Entrada 3

7 3
1 2 2 4 5 5
1 3
3 7
6 1

Salida 3

2
2 3

Entrada 4

4 3
1 2 3
1 4
4 1
1 4

Salida 4

3
2 1

Nota

En el primer ejemplo hay dos mensajeros. El primero entrega solicitudes del empleado $1$ al empleado $3$, o en sentido contrario. Por ejemplo, al entregar una solicitud del empleado $1$ al $3$, primero la transmite del empleado $1$ al $2$, y luego del $2$ al $3$. El segundo mensajero entrega solicitudes del empleado $1$ al $4$, o en sentido contrario. Por ejemplo, al entregar una solicitud del empleado $4$ al $1$, primero la transmite del empleado $4$ al $2$, y luego del $2$ al $1$. El grado de duplicación de esta pareja es $1$, porque ambos recorren el paso entre el empleado $1$, el director, y el empleado $2$.

En el segundo ejemplo también hay dos mensajeros, pero sus recorridos no se solapan.

El tercer ejemplo está representado en la figura anterior. Las líneas gruesas indican los pasos entre empleados. Las líneas finas indican el recorrido del primer mensajero entre los empleados $1$ y $3$. Las líneas con guiones largos indican el recorrido del segundo mensajero entre los empleados $3$ y $7$. Las líneas con guiones cortos indican el recorrido del tercer mensajero entre los empleados $1$ y $6$.

Los recorridos del primer y del segundo mensajero solo comparten el paso entre los empleados $2$ y $3$. Los recorridos del primero y del tercero solo comparten el paso entre los empleados $1$ y $2$. Los recorridos del segundo y del tercero comparten dos pasos: entre los empleados $2$ y $4$, y entre los empleados $4$ y $5$. Por tanto, la pareja de mensajeros $2$ y $3$ tiene el mayor grado de duplicación, igual a $2$.

En el cuarto ejemplo, todos los mensajeros llevan solicitudes entre el director y el empleado $4$. Por tanto, todas las parejas tienen un grado de duplicación igual a $3$. Se permite imprimir cualquier pareja.

Información general sobre los problemas de la segunda sesión

Acceso a los resultados de evaluación durante la sesión

En todos los problemas puedes solicitar el resultado de la evaluación definitiva un número ilimitado de veces. Para cada subtarea se comunican sus puntos y el resultado del programa en cada caso de prueba.

Límite del tamaño del código fuente de la solución

En todos los problemas, el archivo del código fuente de la solución no debe superar los 256 KB.

Proceso de evaluación

En todos los problemas, los puntos de una subtarea solo se conceden si se superan todos sus casos de prueba. La tabla de puntuación indica las subtareas necesarias para cada subtarea. Sus pruebas solo se ejecutan si se han superado todas las subtareas necesarias.

Nota

En los problemas con entradas grandes, el jurado recomienda a quienes usen lenguajes del grupo C/C++ enviar sus soluciones con el compilador LINUX GNU C++ y leer los datos mediante scanf.

Ten en cuenta que en esta sesión se pueden enviar soluciones en Java y Python, así como soluciones del problema interactivo bajo el sistema operativo Ubuntu Linux.