Masala #0472
Sayohatchi
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.
# | input.txt | output.txt |
---|---|---|
1 |
3 2 1 2 1 3 |
3 |
2 |
7 5 2 6 1 3 1 5 3 4 1 2 6 7 |
6 |
3 |
7 6 1 2 1 3 6 3 3 7 4 2 2 5 |
6 |