- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
کاکا پس از تلاش های ناموفق برای کشتن راک تصمیم گرفت با کمک افراد دیگر او را ترور کند. او در شهری زندگی می‌کند که $n$ میدان و $n - 1$ خیابان دوطرفه دارد که هریک دو میدان متفاوت را به هم متصل می‌کند. از هر میدان می‌توان به میدان‌های دیگر رفت (به عبارت دیگر یک درخت است).
میدان‌هایی که دقیقاً یک خیابان به آن‌ها متصل است (برگ های درخت) به خارج شهر راه دارند.
می‌دانیم راک در ابتدا در میدان $k$ است و می‌خواهد به یک برگ برسد تا از شهر خارج شود و کاکا می‌خواهد از خارج شهر تعدادی از افرادش را در تعدادی از برگ‌ها مستقر کند.
راک و افراد کاکا در هر ساعت می‌توانند یک خیابان (متصل به میدان کنونی‌شان) را طی کنند یا در جای خود بمانند و اگر راک و یکی از افراد کاکا در یک لحظه در یک نقطه (درون یک میدان یا یک خیابان) باشند آنگاه راک توسط افراد کاکا ترور می‌شود. دقت کنید راک و افراد کاکا همیشه موقعیت همدیگر را میدانند.
چون افراد بیشتر برای کاکا هزینه بالاتری دارد می‌خواهد حداقل تعداد افرادی را پیدا کند که راک را بتواند ترور کند. شما باید به کاکا در پیدا کردن این عدد کمک کنید.
دقت کنید که اگر پاسخ شما عدد $x$ باشد، یعنی:
- کاکا روشی برای مستقر کردن $x$ نفر در برگ‌ها دارد که راک به هر روشی عمل کند افراد کاکا بتوانند او را ترور کنند.
- به ازای هر عدد $y < x$، اگر تعداد افراد کاکا $y$ باشد، همواره راک روشی برای فرار از دست افراد کاکا دارد (مستقل از نحوه کار افراد کاکا).
ورودی
در خط اول اعداد $n$ و $k$ تعداد میدان‌ها و میدانی که راک قرار گرفته، به ترتیب داده شده‌اند.
$$ 1 \le k \le n \le 10^5 $$
سپس در هر کدام از $n-1$ خط بعدی دو عدد $u$ و $v$ آمده است که نشان دهنده وجود خیابان بین دو میدان $u$ و $v$ است.
تضمین می‌شود گراف میدان‌ها و خیابان‌های بینشان یک درخت است. میدان k حداقل 2 همسایه دارد و برگ نیست.
خروجی
در تنها خط خروجی کمینه تعداد افرار مورد نیاز برای ترور راک را چاپ کنید.
مثال
ورودی نمونه ۱
7 1
1 2
1 3
3 4
3 5
4 6
5 7
خروجی نمونه ۱
3
ارسال پاسخ برای این سؤال