یک درخت ‎$n$‎ راسی به شما داده شده است. روی هر یک از یال های درخت عددی بین ‎$1$‎ و ‎$n-1$‎ نوشته شده و همه این اعداد متمایز هستند. به مسیر بین دو راس ‎$i$‎ و ‎$j$‎ ‎ مناسب می‌گوییم ‎ اگر

• $i$‎ و ‎$j$‎ متفاوت باشند
• ‎ هیچ کدام از اعداد نوشته شده بر روی یال های مسیر بر دیگری بخشپذیر نباشد

شما باید برنامه‌ای بنویسید که با دریافت اطلاعات درخت تعداد میسرهای مناسب آن را پیدا کند‎.

• در سطر اول ورودی، عدد ‎$n$‎، تعداد رئوس درخت قرار دارد.
• در ‎$n-1$‎ سطر بعدی در هر سطر به ترتیب سه عدد ‎$u$‎ ، ‎$v$‎ و ‎$c$‎ آمده است که نشان می‌دهد یک یال بین دو راس ‎$u$‎ و ‎$v$‎ درخت قرار دارد که عدد نوشته شده روی آن ‎$c$‎ است‎.‎
• همه‌ی اعداد نوشته شده روی یال‌های درخت متفاوت و بین ‎$1$‎ و ‎$n-1$‎ هستند. هم‌چنین ورودی یک درخت را توصیف می‌کند.‎
• ‎$1 \le n \le 100000$‎
• در حداقل ‎$40$‎ درصد تست‌ها ‎$n$‎ از ‎$3000$‎ بیش‌تر نیست.‎

در تنها سطر خروجی پاسخ سوال را چاپ نمایید.‎

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

در مثال نمونه مسیرهای بین رئوس ‎$(1,2)$‎ ، ‎$(1,3)$‎ ، ‎$(2,3)$‎ و ‎$(2,4)$‎ مناسب هستند‎.

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