Zəncirin təmiri

Sovunyada $n$ halqadan ibarət bir zəncir var idi, halqalar $1$-dən $n$-ə qədər nömrələnmişdi. Amma zəncir çarpayının çəkicəsində qalanda tamam dolaşıb. Sovunya vəziyyəti düzəltmək istəyir.

Hər bir halqa məftildən düzəldilmiş bir halqadır. Hər iki halqa ya bir-birinə bərkidilib, ya da yox. Sovunya kömək üçün Pina müraciət etdi. O, iki əməliyyat edə bilər:

• Bir halqanı açmaq. Bu zaman, o bitişik halqa olmaqdan çıxır və həmin halqanı digər halqalardan ayırmaq olar.

• Əvvəlcədən açılmış halqanı yenidən qaynaq etmək. Bu zamanda, o yenidən bitişik halqaya çevrilir. Pin əvvəlcə digər halqalardan ixtiyari bir dəstəni seçib, cari halqanı qaynaq etmədən əvvəl onların içindən keçirə bilər və beləliklə seçilmiş dəstənin hər bir halqası ilə bu halqanı bərkidə bilər.

Sonda bütün halqalar qaynaqlanmış olmalıdır.

Sovunya istəyir ki, $1$ nömrəli halqa $2$ nömrəli halqa ilə, $2$ nömrəli $3$ ilə, ..., $n-1$ nömrəli isə $n$ ilə birləşmiş olsun. Başqa sözlə, $i$ və $i+1$ nömrəli halqalar bütün $i\in [1,n-1]$ üçün bərkidilmiş olsun. Və başqa heç bir halqa cütlüyü birləşdirilməsin.

Pina zənciri düzəltmək üçün minimum əməliyyat sayını müəyyənləşdirməkdə kömək edin.

Giriş verilənləri

Birinci sətirdə iki tam ədəd $n$ və $m(1\le n\le 40,0\le m\le n\cdot (n-1)/2)$ — halqaların sayı və ilkin bərkidilmiş halqa cütlərinin sayı verilir.

Sonrakı $m$ sətirdə $a_i$ və $b_i(1\le a_i,b_i\le n,a_i\ne b_i)$ iki tam ədəd verilir — bərkidilmiş halqaların nömrələri.

Girişdə hər bir qeyri-sıralı halqa cütlüyünün maksimum bir dəfə rast gəlindiyinə zəmanət verilir.

Çıxış verilənləri

Bir tam ədəd çıxarın — zənciri düzəltmək üçün Pin tərəfindən ediləcək minimum əməliyyat sayı.

Nümunələr

Birinci misalda Pin $3$ nömrəli halqanı aça bilər. Bu zaman o, digər qalan halqalardan çıxar. Sonra $3$ nömrəli halqanı yenidən qaynaqlayaraq yalnız $2$ nömrəli halqa ilə bərkidə bilər.

İkinci misalda Pin $2$ nömrəli halqanı aça bilər, sonra onu qaynaqlayaraq $1$ və $3$ nömrəli halqalarla birləşdirir. Daha sonra $4$ nömrəli halqanı açıb, qaynaq edərək $3$ və $5$ nömrəli halqalarla birləşdirir.