Pistolet Annihilateur#11727
Dans le système Link-Cut, il y a planètes, chacune avec son propre type. Le type d'une planète est un entier allant de à . Vous recevez un tableau d'entiers a_1, a_2, \dots, a_n représentant les types de chaque planète. Votre objectif est de faire en sorte que toutes les planètes soient du même type ou de déterminer qu'il est impossible de le faire.
Pour y parvenir, Lucy a construit un pistolet annihilateur pour vous, qui peut changer les types de chaque planète en n'importe quel autre type (de à ) qui n'est pas égal à leur type précédent en une seule utilisation. Les nouveaux types de planètes n'ont pas nécessairement à être distincts.
Plus formellement, lors d'une utilisation du pistolet, vous pouvez créer un tableau x_1, x_2, \dots, x_n d'entiers allant de à tel que x_i \neq a_i pour tout , puis attribuer à chaque élément du tableau a_i une nouvelle valeur x_i.
Étant donné que l'utilisation du pistolet annihilateur est assez gourmande en ressources, et que vous devez économiser des ressources pour capturer le maléfique Chmyaaax, vous devez atteindre l'objectif en un minimum d'utilisations du pistolet. Votre tâche est de déterminer ce nombre ou de déterminer qu'il est impossible de faire en sorte que toutes les planètes soient d'un même type.
La première ligne contient deux entiers et (1 \le n, k \le 10^5) — le nombre de planètes et le nombre de types possibles pour chaque planète.
La deuxième ligne contient entiers a_1, a_2, \dots, a_n (1 \le a_i \le k) — les types des planètes.
Dans une seule ligne, vous devez afficher le nombre minimum d'utilisations du pistolet annihilateur nécessaires pour faire en sorte que toutes les planètes soient du même type ou s'il est impossible de le faire.
Exemple
Exemple 1
Exemple 2
Exemple 3
Dans le premier exemple, vous pouvez faire la seule utilisation du pistolet, en changeant les types des deux planètes en . Puisque leurs types initiaux sont différents, la réponse ne peut pas être .
Dans le deuxième exemple, il peut être montré qu'il n'est pas possible de faire en sorte que les deux planètes soient du même type.
Dans le troisième exemple, toutes les planètes ont le même type initialement, donc vous n'avez rien à faire.
Dans le quatrième exemple, vous pouvez utiliser le pistolet deux fois :
[1, 2, 3, 1] - [2, 3, 2, 3]
[2, 3, 2, 3] - [1, 1, 1, 1]
Il peut être montré que la condition ne peut pas être satisfaite en une seule utilisation du pistolet.
( points): n = 1;
( points): k = 1;
( points): n = 2;
( points): k = 2;
( points): n \le 100,\,k \le 100;
( points): pas de contraintes supplémentaires.