Masala #0181

Sizga o’rmon berilgan (oddiy bog’lanishlardan iborat, sikl mavjud bo’lmagan graf). 

Har bir daraxtda tugunlar soni juft bo’ladigan qilib o’rmondan maksimal sondagi qirralarni olib tashlang.

Misol uchun tugunlar soni 4 bo’lgan quyidagi daraxtdan 1 ta qirrani olib tashlash mumkin:

Dastlabki satrda ikkita butun son, N va M (0 < M < N ≤ 100) – o’rmondagi barcha daraxtlarning jami tugunlar soni va jami qirralar soni. Keyingi M ta qatorda har bir qirra bog’lab turgan tugunlar juftligi kiritiladi.

Har bir daraxtda tugunlar soni juft bo’ladigan qilib o’rmondan maksimal nechta qirrani olib tashlash mumkinligini chop eting. Yechim mavjudligi kafolotlanadi.