در یک شهر تعداد $N$ دهکده با شماره‌های $1, 2, \cdots, N$ قرار دارند که با $N-1$ جاده به هم وصل شده‌اند. هر جاده دقیقاً دو دهکده را به هم وصل می‌کند و از هر روستا به بقیه روستاها با استفاده از این جاده‌ها می‌توان رسید. طول هر جاده $1$ واحد است.

برای اطمینان از امنیت مردمِ شهر، هر روز گشت پلیس شهر باید از تمام جاده‌ها عبور کند. ایستگاه پلیس در روستای شماره $1$ قرار دارد، در نتیجه گشت زنی باید از روستای $1$ شروع و در نهایت با بازگشت به روستای $1$ در پایان روز ختم شود.

مثال زیر که یک شهر با $8$ روستا را نشان می‌دهد را در نظر بگیرید. روستاها با دایره و روستای $1$ با یک دایره سیاه نشان داده شده است. جاده‌ها خطوط اتصال این روستاها است. برای گذشتن از همه جاده‌ها، گشت باید $14$ واحد در هر روز طی کند. توجه داشته باشید که گشت باید از هر راه دو بار عبور کند تا کار روزانه‌اش به اتمام برسد.

برای کاهش کل مسافت گشت، شهر تصمیم به ساختن $K$ میانبر جدید بین روستاها گرفته است. هر میانبر می‌تواند دو روستای دلخواه را بهم وصل کند. دو میانبر می‌توانند در یک روستا مشترک باشند (مثال $c$). میانبر حتی می تواند حلقه باشد یعنی یک روستا را به خودش وصل کند. بودجه محدود است، در نتیجه $K$ همواره $1$ یا $2$ است. همچنین برای اطمینان از هدر نرفتن پول، گشت باید از هر میانبر دقیقاً یک بار در روز عبور کند. مثال‌های زیر را در نظر بگیرید:

در مثال $a$ یک میانبر ساخته شده و مجموع مسافت روزانه $11$ شده است. در مثال $b$ دو میانبر ساخته شده و مجموع مسافتی که گشت در هر روز می‌پیماید برابر $10$ است. در مثال آخر $c$ نیز دو میانبر ساخته شده ولی شرط عبور دقیقاً یک بار از هر میانبر، مجموع مساحت را به $15$ رسانده است.

برنامه‌ای بنویسید که با گرفتن اطلاعات جاده‌ها و تعداد میانبرها، جای میانبرهایی را که مجموع مسافت گشت را کمینه می‌کنند پیدا کند.

• خط اول شامل دو عدد صحیح N و $1 \leq K \leq 2$ می‌باشد.
• هر یک از $N-1$ خط بعدی بیانگر یک جاده می‌باشد.
• هر یک از این خطوط شامل دو عدد صحیح $A$ و $B$ ($1\leq A, B \leq N$) است که نشان می‌دهد یک جاده روستاهای $A$ و $B$ را به هم وصل کرده است.
• در ۱۰ درصد از تست‌ها $N \leq 1,000$ و $K=1$
• در ۳۰ درصد از تست‌ها $K=1$
• در ۸۰ درصد از تست‌ها حداکثر تعداد جاده‌های متصل به هر روستا برابر است با $25$
• در ۹۰ درصد از تست‌ها حداکثر تعداد جاده‌های متصل به هر روستا برابر است با $150$
• در ۱۰۰ درصد از تست‌ها $3\leq N \leq 100,000$ و $1\leq K\leq 2$

در تنها سطرِ خروجی یک عدد صحیح را که بیانگر کم‌ترین مسافتی است که پس از ساختن $K$ میانبر گشت در هر روز باید طی کند، بنویسید.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل