Masala #0472

Abdullajon yerga sayohatidan so’ng o’z ona sayyorasiga qaytdi va u yerda oz muddat yashaganidan so’ng yana sayohatga chiqqisi kelib qoldi. Endigi gal u o’z sayohatini shaharlar orasidagi yo’llar daraxtsimon bo’lgan bir sayyoraga borishga qaror qildi. Bu sayyorada jami N ta shahar bor, shaharlar aro jami N-1 ta ikki tomonlama harakat qiladigan poyezdlar mavjud. Abdullajon bu sayyoraga sayohatini ixtiyoriy shahardan boshlashi mumkin. Afsuski bu sayyorada Abdullajonning noyob qobiliyatlari ishlamas ekan, ya’ni, u ketmon yoki boshqa buyumni uchira olmas, pul ishlab chiqara olmas ekan. Shu sababli Abdullajon bir shahardan boshqa shaharga borish uchun poyezddan foydalanishga qaror qilibdi, cho’ntagidagi pul jami K ta poyezd chiptasiga yetarli ekanligini bilganidan so’ng Abdullajon ko’pi bilan nechta shaharni aylanishi mumkinligini bilmoqchi. Buni aniqlashda Abdullajonga yordam bering.

Eslatma: Abdullajon sayohatni ixtiyoriy shahardan boshlashi va ixtiyoriy shaharda to’xtatishi mumkin. 1 ta poyezd chiptasi bir shahardan unga qo’shni (orasida poyezd bor) shaharga o’tish imkonini beradi.

Kirish faylining dastlabki satrida ikkita butun son, \(N (1 \le N \le 10^5)\) va \(K(0 \le K \le 10^6)\) sonlari kiritiladi.

Keyingi N-1 ta qatorda poyezd bilan ulangan shaharlar juftliklari kiritiladi (Shaharlar 1 dan N gacha nomerlangan holda ifodalangan).

Chiqish faylida Abdullajon sayohat davomida ko’pi bilan nechta shaharda bo’la olishini aniqlang.