Trees
گراف همبند G به ما داده شده است. میدانیم هیچ 2 دور از این گراف دارای یال مشترک نیستند.
یالهای گراف G را به تعدادی درخت T1 تا Tk افراز کردهایم (رئوس هر کدام از Tiها زیر مجموعهای از رئوس G هستند). شما باید با حذف کمترین تعداد از این درختها از گراف G کاری کنید که گراف حاصل دور نداشته باشد.
ورودی
ورودی با ۲ عدد صحیح به صورت N M شروع خواهد شد. N تعداد راسها و M تعداد یالهای گراف میباشد.
در هر یک از M خط بعدی سه عدد طبیعی به صورت uiviti آمده است که ui و vi بیانگر راسهای دو سر یال و ti شماره درختی است که این یال (در افراز گراف به درختها) به آن تعلق دارد.
درختها از 1 تا k شمارهگذاری شدهاند.
1≤N≤10000
N−1≤M≤(3×(N−1))/2
1≤k≤10000
خروجی
در خروجی یک عدد صحیح که بیانگر حداقل تعداد درختهایی که باید حذف شوند است را بنویسید.
محدودیتها
ورودی و خروجی نمونه
ورودی نمونه | خروجی نمونه |
6 6
1 5 1
1 2 2
2 4 2
2 6 3
3 4 1
3 5 1 | 1 |