====== 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$ ===== خروجی ===== در خروجی یک عدد صحیح که بیانگر حداقل تعداد درخت‌هایی که باید حذف شوند است را بنویسید. ===== محدودیت‌ها ===== * محدودیت زمان: ۱ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |6 6 \\ 1 5 1‎ \\ 1 2 2‎ \\ 2 4 2‎ \\ 2 6 3‎ \\ 3 4 1‎ \\ 3 5 1‎ | 1 | * [[سوال ۴|سوال بعد]] * [[سوال ۲|سوال قبل]]