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

فربد برای تنوع ذهنی مدتی است برنامه‌نویسی الگوریتمی را کنار گذاشته و به باغبانی روی آورده. حال فصل زمستان از راه رسیده و او می‌خواهد درخت‌های خود را هرس کند. از آنجا که تفکر الگوریتمی در تمام زندگی یار اوست او می‌خواهد هرس را طوری انجام دهد که آویزانی ریشه کمینه می‌شود. به عبارت دیگر درخت‌های ریشه‌دار او شبیه درخت‌های ریشه‌دار می‌مانند. یعنی می‌توان آنها را با گرافی $n$ راسی، همبند و بدون دور مدل کرد و راس شماره یک را به عنوان ریشه در نظر گرفت. میزانه آویزانی یک برگ برابر ۱ است و آویزانی رئوس دیگر برابر یک به‌علاوه بیشینه آویزانی بچه‌های آن تعریف می‌شود. همانطور که گفته‌شد او نمی‌خواهد دست به کد شود پس به او کمک کنید.

توجه کنید که او چون درخت خود را دوست دارد نمی‌خواهد بیشتر از $k$ بار آن را هرس کند و در هر عملیات هرس او دقیقا یک برگ درخت به همراه یال متصل به آن را حذف می‌کند. همچنین راسی ممکن است در ابتدا برگ نباشد و پس از تعدادی هرس به برگ تبدیل شود و نیز ریشه درخت هرس نشدنی است.

ورودی

در سطر اول ورودی $t$ به عنوان تعداد درخت‌های فربد می‌آید. سپس اطلاعات $t$ درخت به شرح زیر می‌آید.

در سطر اول اطلاعات درخت $r$ عدد $n_r$ تعداد رئوس درخت و $k_r$ حداکثر تعداد هرس‌های مجاز می‌آید.

سپس در سطر $i$ از $n-1$ سطر بعد در هر سطر دو عدد $u_{ri}$ و $v_{ri}$ می‌آید که نشان‌دهنده وجود یک یال بین آن دو راس است. تضمین می‌شود گراف ورودی درخت است. $$t \le 10 , 000$$ $$1 \le n_i, \sum_{r=1}^t n_r \le 500 , 000 \quad (1 \le i \le t)$$ $$0 \le k_r \le n_r-1 \quad (1 \le r \le t)$$ $$1 \le u_{ri}, v_{ri} \le n_r$$

خروجی

به ازای هر درخت کمینه آویزانی ریشه پس از هرس کردن حداکثر $k$ برگ را در خطوط متفاوت خروجی دهید.

مثال

ورودی نمونه ۱

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

خروجی نمونه ۱

1
3

در درخت اول، فربد می‌تواند رأس‌های با شماره‌های ۲ و ۳ را هرس کند. پس از این کار تنها رأس باقی‌مانده رأس شماره‌ی ۱ خواهد بود که از آن‌جایی که هیچ فرزندی ندارد برگ حساب می‌شود و آویزانی آن برابر ۱ خواهد بود.

در درخت دوم، فربد رأس شماره‌ی ۶ را حذف می‌کند و بدین‌ترتیب آویزانی درخت برابر ۳ خواهد شد.