Annihilator Silahı#11727
Link-Cut sistemində planet var, hər birinin öz növü var. Bir planetin növü -dən -ya qədər olan tam ədəddir. Hər bir planetin növünü təmsil edən a_1, a_2, \dots, a_n tam ədəd arrayi verilir. Sizin məqsədiniz bütün planetləri eyni növə çevirməkdir, ya da bunun mümkün olmadığını müəyyən etməkdir.
Bunu əldə etmək üçün, Lusi sizin üçün bir annihilator silahı düzəldib, bu silah hər bir planetin növünü bir istifadə ilə əvvəlki növü ilə bərabər olmayan istənilən digər növə (-dən -ya qədər) dəyişə bilər. Planetlərin yeni növləri mütləq fərqli olmalı deyil.
Daha rəsmi şəkildə, silahın bir istifadəsində, -dən -ya qədər olan tam ədədlərdən ibarət x_1, x_2, \dots, x_n arrayini yarada bilərsiniz ki, x_i \neq a_i olsun bütün üçün, və sonra arrayin hər bir elementi a_i-yə yeni dəyər x_i təyin edə bilərsiniz.
Annihilator silahını istifadə etmək olduqca resurs tələb edir və siz pis Chmyaaax-ı ələ keçirmək üçün resursları saxlamaq lazımdır, buna görə də məqsədə minimum sayda silah istifadəsi ilə çatmalısınız. Sizin vəzifəniz bu sayı müəyyən etməkdir, ya da bütün planetləri bir növə çevirməyin mümkün olmadığını müəyyən etməkdir.
Birinci sətirdə iki tam ədəd və (1 \le n, k \le 10^5) — planetlərin sayı və hər planet üçün mümkün növlərin sayı.
İkinci sətirdə tam ədəd a_1, a_2, \dots, a_n (1 \le a_i \le k) — planetlərin növləri verilir.
Bir sətirdə, bütün planetləri eyni növə çevirmək üçün tələb olunan minimum silah istifadəsi sayını və ya bunun mümkün olmadığını göstərmək üçün çap etməlisiniz.
Nümunə
Nümunə 1
Nümunə 2
Nümunə 3
Birinci nümunədə, silahın tək istifadəsini edə bilərsiniz, hər iki planetin növünü -ə dəyişərək. Onların ilkin növləri fərqli olduğuna görə, cavab ola bilməz.
İkinci nümunədə, hər iki planetin eyni növə çevrilməsinin mümkün olmadığını göstərmək olar.
Üçüncü nümunədə, bütün planetlərin ilkin növləri eynidir, buna görə də heç nə etməyə ehtiyac yoxdur.
Dördüncü nümunədə, silahı iki dəfə istifadə edə bilərsiniz:
[1, 2, 3, 1] - [2, 3, 2, 3]
[2, 3, 2, 3] - [1, 1, 1, 1]
Bir istifadədə şərtin yerinə yetirilməsinin mümkün olmadığını göstərmək olar.
( xal): n = 1;
( xal): k = 1;
( xal): n = 2;
( xal): k = 2;
( xal): n \le 100,\,k \le 100;
( xal): əlavə məhdudiyyət yoxdur.