Pistola Aniquiladora#11727
En el sistema Link-Cut, hay planetas, cada uno con su propio tipo. El tipo de un planeta es un entero que varía de a . Se te da un arreglo de enteros a_1, a_2, \dots, a_n que representan los tipos de cada planeta. Tu objetivo es hacer que todos los planetas sean del mismo tipo o determinar que es imposible.
Para lograr esto, Lucy ha construido una pistola aniquiladora para ti, que puede cambiar los tipos de cada planeta a cualquier otro tipo (de a ) que no sea igual a su tipo anterior en un solo uso. Los nuevos tipos de los planetas no necesariamente tienen que ser distintos.
Más formalmente, en un uso de la pistola, puedes crear un arreglo x_1, x_2, \dots, x_n de enteros de a tal que x_i \neq a_i para todo , y luego asignar a cada elemento del arreglo a_i un nuevo valor x_i.
Dado que usar la pistola aniquiladora es bastante intensivo en recursos, y necesitas ahorrar recursos para capturar al malvado Chmyaaax, debes lograr el objetivo en el mínimo número de usos de la pistola. Tu tarea es determinar este número o determinar que es imposible hacer que todos los planetas sean de un tipo.
La primera línea contiene dos enteros y (1 \le n, k \le 10^5) — el número de planetas y el número de tipos posibles para cada planeta.
La segunda línea contiene enteros a_1, a_2, \dots, a_n (1 \le a_i \le k) — los tipos de los planetas.
En una sola línea, necesitas imprimir el número mínimo de usos de la pistola aniquiladora requeridos para hacer que todos los planetas sean del mismo tipo o si es imposible.
Ejemplo
Ejemplo 1
Ejemplo 2
Ejemplo 3
En el primer ejemplo, puedes hacer el único uso de la pistola, cambiando los tipos de ambos planetas a . Dado que sus tipos iniciales son diferentes, la respuesta no puede ser .
En el segundo ejemplo, se puede demostrar que no es posible hacer que ambos planetas sean del mismo tipo.
En el tercer ejemplo, todos los planetas tienen el mismo tipo inicialmente, por lo tanto, no necesitas hacer nada.
En el cuarto ejemplo, puedes usar la pistola dos veces:
[1, 2, 3, 1] - [2, 3, 2, 3]
[2, 3, 2, 3] - [1, 1, 1, 1]
Se puede demostrar que la condición no se puede satisfacer en un solo uso de la pistola.
( puntos): n = 1;
( puntos): k = 1;
( puntos): n = 2;
( puntos): k = 2;
( puntos): n \le 100,\,k \le 100;
( puntos): sin restricciones adicionales.