Annihilator Silahı

Link-Cut sistemində $n$ planet var, hər birinin öz növü var. Bir planetin növü $1$-dən $k$-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ə ($1$-dən $k$-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ə, $1$-dən $k$-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\ne a_i$ olsun bütün $i$ üçü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.

Giriş verilənləri

Birinci sətirdə iki tam ədəd $n$ və $k$ $(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ə $n$ tam ədəd $a_1,a_2,\dots ,a_n$ $(1\le a_i\le k)$ — planetlərin növləri verilir.

Çıxış verilənləri

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 $-1$ çap etməlisiniz.

Nümunələr

Qeyd

Birinci nümunədə, silahın tək istifadəsini edə bilərsiniz, hər iki planetin növünü $3$-ə dəyişərək. Onların ilkin növləri fərqli olduğuna görə, cavab $0$ 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. $[1,2,3,1]-[2,3,2,3]$

2. $[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.

Qiymətləndirmə

1. ($2$ xal): $n=1$;

2. ($4$ xal): $k=1$;

3. ($8$ xal): $n=2$;

4. ($8$ xal): $k=2$;

5. ($10$ xal): $n\le 100,k\le 100$;

6. ($18$ xal): əlavə məhdudiyyət yoxdur.