Trees

گراف همبند $G$ به ما داده شده است. می‌دانیم هیچ $2$ دور از این گراف دارای یال مشترک نیستند. یال‌های گراف $G$ را به تعدادی درخت $T_1$ تا $T_k$ افراز کرده‌ایم (رئوس هر کدام از $T_i$ها زیر مجموعه‌ای از رئوس $G$ هستند). شما باید با حذف کم‌ترین تعداد از این درخت‌ها از گراف $G$ کاری کنید که گراف حاصل دور نداشته باشد.

• ورودی با ۲ عدد صحیح به صورت $N \ M$ شروع خواهد شد. $N$ تعداد راس‌ها و $M$ تعداد یال‌های گراف می‌باشد.
• در هر یک از $M$ خط بعدی سه عدد طبیعی به صورت $u_i v_i t_i$ آمده است که $u_i$ و $v_i$ بیانگر راس‌های دو سر یال و $t_i$ شماره درختی است که این یال (در افراز گراف به درخت‌ها) به آن تعلق دارد.
• درخت‌ها از $1$ تا $k$ شماره‌گذاری شده‌اند.
• $1 \leq N \leq 10000$
• $N-1 \leq M \leq (3×(N-1))/2$
• $1 \leq k \leq 10000$

در خروجی یک عدد صحیح که بیانگر حداقل تعداد درخت‌هایی که باید حذف شوند است را بنویسید.

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

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