یک درخت $n$ راسی به شما داده شده است که راس‌های آن از $1$ تا $n$ شماره گذاری شده اند. هر راس در این درخت با یکی از رنگ‌های $1$ تا $k$ رنگ‌آمیزی شده است.

مقدار مطلوبیت هر راس به شکل زیر تعریف می‌شود:

• فرض کنید پس از کندن راس $v$ از درخت، $t$ مولفه‌ی همبندی به وجود بیاید. این مولفه‌ها را $a_1, a_2, \dots, a_t$ می‌نامیم.
• به ازای هر مولفه $a_i$، مجموعه‌ی رنگ‌های راس‌های آن را $s_i$ می‌نامیم. دقت‌کنید که در مجموعه عضو تکراری نداریم و اندازه‌ی یک مجموعه برابر با تعداد اعضای متفاوت آن می‌باشد.
• مقدار مطلوبیت راس $v$ برابر است با $\sum_{i=1}^t{|s_i|}$.

مقدار مطلوبیت تمام راس‌های درخت را محاسبه کنید.

در خط اول ورودی دو عدد طبیعی $n$ و $k$، نشان‌دهنده‌ی تعداد راس‌های درخت و حداکثر شماره‌ی رنگ راس‌های درخت، آمده است.

در خط دوم ورودی $n$ عدد طبیعی $c_1, c_2, \dots, c_n$، نشان‌دهنده‌ی رنگ‌های راس‌های درخت، آمده است.

در $n-1$ خط بعدی ورودی، در هر خط دو عدد طبیعی $v_i$ و $u_i$ آمده است که نشان‌دهنده‌ی وجود یک یال بین دو راس $v_i$ و $u_i$ است.

در تنها خط خروجی، $n$ عدد چاپ کنید که عدد $i$ام مقدار مطلوبیت راس $i$ام را نشان می‌دهد.

• زیرمسئله اول (۸ نمره): $n \le 1000$
• زیرمسئله دوم (۸ نمره): $k \le 10$
• زیرمسئله سوم (۸ نمره): درخت داده شده مسیر است.
• زیرمسئله چهارم(۱۹ نمره): از هر رنگ حداکثر دو راس موجود است.
• زیرمسئله پنجم(۵۷ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \le k \le n \le 3 \times 10^5$
• $1 \le c_i \le k$
• $1 \le u_i, v_i \le n$
• تضمین می‌شود گراف ورودی درخت است.

• سوال بعد