Masala #UGBYIY0HDS

Qochqin baliqchi Baxtiyor aka hamisha eng katta baliqni tutishga urinadi - ammo uning maxsus baliq tarmog‘i har safar imtihonga duch keladi. Katta baliqlar ba’zan tarmoq ipini uzib yuboradi va Baxtiyor aka uni yamashga majbur bo‘ladi.

Bir kuni, tunda yulduzlarni tomosha qilib o‘tirgan Baxtiyor aka boshini qashib shunday o‘ylab qoldi:

“Agar men tarmog‘imni haddan tashqari ko‘p ishlatsam, u iplar uzilmasdan va baliqlar qochib ketmasdan oldin qanchagacha chiday oladi?

Siz Baxtiyor akaga matematik yordam berishingiz kerak.

🔹 Tarmoq tasviri

Tarmoq to‘rtburchak matritsaga o‘xshaydi, unda M × Nta tugun mavjud. Har bir ikki qo‘shni tugun orasida ip bor.

Bitda ipning uzilishi deb - har qanday qo‘shni tugunlarni bog‘lovchi ipning uzilib ketishi tushuniladi.

Agar juda ko‘p iplar uzilsa, tarmoq ikki yoki undan ortiq bo‘lakka ajrab ketadi va Baxtiyor aka keng kulgan holatda qoldiradi.

🔹 Topshiriq

Berilgan M×N o‘lchamli tarmoqda maksimal nechta ipni uzish mumkin, shunda tarmoq hali ham bitta butun tuzilma bo‘lib turadi? (ya’ni, u hali ajralmagan boʻladi).

Kirish faylining birinchi qatorda ikkita butun son kiritiladi: M va N ( 1 ≤ M, N ≤ 10 000 ), bu yerda:

• M — tarmoqning vertikal yo'nalishdagi tugunlar soni,
• N — tarmoqning gorizontal yo'nalishdagi tugunlar soni.

Chiqish faylida tarmoq buzilmasdan turib uzilishi mumkin boʻlgan maksimal ip (uzilishlar) sonini chiqaring.