سعید و فرتاش مشغول انجام یک بازی بر روی یک درخت $n$ راسی هستند. در این درخت هر راس $v$ دارای یک عدد نامنفی $s_v$ است. در ابتدا هر کدام از این دو نفر دارای یک عدد هستند که برابر با $0$ است. فرض کنید عدد سعید برابر با $x_s$ و عدد فرتاش برابر با $x_f$ باشد.

بازی به این صورت انجام می‌شود که سعید حرکت اول را انجام می‌دهد(چون او انسان هوشمندتری نسبت به فرتاش است) و از این به بعد آن ها یکی در میان بازی می‌کنند. در هر مرحله کسی که نوبت اوست، یکی از برگ‌های درخت را انتخاب می‌کند و آن را از درخت حذف می‌کند. پس از آن عدد خود را برابر با بیشینه خودش و عدد برگ حذف شده قرار می‌دهد. بازی زمانی پایان می‌یابد که همه رئوس درخت حذف شده باشند. در پایان کسی که عددش از دیگری کمتر است برنده بازی خواهد بود و اجازه دارد به اندازه اختلاف عدد دو بازی‌‌کن به بازی‌کن دیگر چَک بزند. در صورتی که عدد سعید و فرتاش برابر باشد هر کدام یک چَک به دیگری می‌زنند.

شما باید برنامه ای بنویسید که با دریافت اطلاعات مربوط به درخت به دست بیاورد با فرض این که دو بازی‌کن بهترین بازی خود را انجام می‌دهند نتیجه بازی به چه صورت خواهد بود.

• در سطر اول ورودی عدد $n$ نشان دهنده تعداد رأس‌ها آمده است.
• در سطر بعدی $n$ عدد آمده است که به ترتیب $s_1$ تا $s_n$ را مشخص می‌کنند. می‌توانید فرض کنید که رأس ها از $1$ تا $n$ شماره‌گذاری شده اند.
• در $n-1$ سطر بعدی در هر سطر اطلاعات یک یال با دو عدد $u_i$ و $v_i$ مشخص شده است.
• تضمین می‌شود که گراف داده شده در ورودی یک درخت را توصیف می‌کند.
• $1 \leq n \leq 10^5$.
• به ازای همه $i$ ها، $1 \leq s_i \leq 10^6$.

در تنها سطر خروجی دو عدد چاپ کنید که عدد اول نشان دهنده تعداد چَک‌هایی است که سعید به فرتاش می‌زند و عدد دوم نشان دهنده تعداد چَک‌هایی است که فرتاش به سعید می‌زند.

• زیرمسئله اول (۲۵ نمره): در همه‌ی تست‌ها $n\leq 20$.
• زیرمسئله دوم (۲۵ نمره): در همه‌ی تست‌ها $n\leq 2\times 10^3$.
• زیرمسئله سوم (۲۵ نمره): در همه‌ی تست‌ها $n\leq 2\times 10^4$.
• زیرمسئله چهارم (۲۵ نمره): در همه‌ی تست‌ها $n\leq 10^5$.

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