يواصل Farmer John بلا توقف إبقاء الأبقار لائقة بالتمرين في طرق المراعي. رؤوس وحواف ثنائية الاتجاه بينها مسار بسيط وحيد لكل زوج، فتشبه شجرة. كل الحواف المتعرجة متساوية الطول على نحو مدهش.

تسمي الأبقار الذكية أكبر مسافة بين رأسين بمجموعة طرق طول المسار، وإن طال كثيرًا رفضت كل تمرين.

رسم $V$ رؤوس ($2 \le V \le 100,000$)، أرقام $1..V$. حجب طريق بين رأسين ينشئ مجموعات أكثر ويقلل طولي المجموعتين.

من شجرة متصلة بالكامل، $S$ حجبات ($1 \le S \le V-1$) تنشئ $S+1$ مجموعات. اختر لتصغير أكبر طول بينها.

كل $V-1$ حواف تصل $A_{i}$ ($1 \le A_{i} \le V$) و$B_{i}$ ($1 \le B_{i} \le V; A_{i} \ne B_{i}$).

مثال خطي بسبعة رؤوس:

                   1---2---3---4---5---6---7

يمكن حجب طريقين هكذا: 1---2 | 3---4 | 5---6---7

أكبر طول $2$ وهو الجواب الأمثل، لا أفضل.

حد الوقت: ثانيتان

حد الذاكرة: 32 MB

الإدخال

• السطر 1: الصحيحان $V$ و$S$ تفصلهما مسافة.
• الأسطر $2..V$: الصحيحان $A_{i}$ و$B_{i}$ تفصلهما مسافة.

الإخراج

• السطر 1: صحيح، أفضل أكبر طول مع $S$ حجبات.

أمثلة

الإدخال 1

7 2
6 7
3 4
6 5
1 2
3 2
4 5

الإخراج 1

2

مؤلف المسألة: Michael Cohen، 2010