Ordenación de agujeros de gusano.
Las vacas del Granjero Juan se han cansado de su pedido diario de que ellas se ordenen antes de dejar el establo cada mañana. Ellas acaban de completar sus doctorados en fisica cuantica, y estan listas a acelerar un poco las cosas. Esta mañana, como es usual, las vacas del Granjero Juan , convenientemente numeradas , estan acantonadas en el establo en posiciones distintas, tambien numeradas , de tal manera que la vaca esta en la posicion . Pero esta mañana también hay agujeros de gusano , numeradas , donde el agujero de gusano conecta bidireccionalmente la posicion con la posicion y tiene ancho , , .
En cualquier momento, dos vacas situadas en extremos opuestos de un agujero de gusano pueden optar por intercambiar simultáneamente sus lugares a través del agujero de gusano. Las vacas deben realizar dichos intercambios hasta que la vaca esté en la ubicación para .
Las vacas no quieren ser aplastadas por los agujeros de gusano. Ayúdales a maximizar la anchura del agujero de gusano menos ancho que deben utilizar para ordenarse. Se garantiza que es posible que las vacas se ordenen a sí mismas.
Entrada
La primera línea contiene dos enteros, y . La segunda línea contiene los enteros . Se garantiza que es una permutación de .
Para cada entre 1 y , la línea contiene los enteros y .
Salida
Un único número entero: la máxima anchura mínima de los agujeros de gusano en los que debe meterse una vaca durante el proceso de clasificación. Si las vacas no necesitan ningún agujero de gusano para clasificarse, la salida es -1.
Ejemplo #1 de Entrada
4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 3
Ejemplo #1 de Salida
9
Esta es una forma posible de ordenar las vacas utilizando sólo agujeros de gusano de una anchura mínima de 9:
La vaca 1 y la vaca 2 intercambian sus posiciones utilizando el tercer agujero de gusano. La vaca 1 y la vaca 3 intercambian sus posiciones utilizando el primer agujero de gusano. La vaca 2 y la vaca 3 intercambian sus posiciones utilizando el tercer agujero de gusano.
Ejemplo #2 de Entrada
4 1
1 2 3 4
4 2 13
Ejemplo #2 de Salida
-1
No se necesitan agujeros de gusano para ordenar las vacas.
Calificación
Los casos 3-5 satisfacen . Los casos 6-10 no satisfacen restricciones adicionales.
Comments