Zəncirin təmiri#11060
Sovunyada halqadan ibarət bir zəncir var idi, halqalar -də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, nömrəli halqa nömrəli halqa ilə, nömrəli ilə, ..., n - 1 nömrəli isə ilə birləşmiş olsun. Başqa sözlə, 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.
Birinci sətirdə iki tam ədəd 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ı 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.
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ı.
Birinci misalda Pin nömrəli halqanı aça bilər. Bu zaman o, digər qalan halqalardan çıxar. Sonra nömrəli halqanı yenidən qaynaqlayaraq yalnız nömrəli halqa ilə bərkidə bilər.
İkinci misalda Pin nömrəli halqanı aça bilər, sonra onu qaynaqlayaraq və nömrəli halqalarla birləşdirir. Daha sonra nömrəli halqanı açıb, qaynaq edərək və nömrəli halqalarla birləşdirir.
Nümunə 1
Nümunə 2
Nümunə 3