Masala #0472

Xotira 32 MB Vaqt 1000 ms
14

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.


Kiruvchi ma'lumotlar:

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).


Chiquvchi ma'lumotlar:

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


Misollar
# 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