هیتلر مخفی


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

در گذشته‌ای نه چندان دور nn کشور داشتیم که یکی از آن‌ها آلمان نازی بود و به رهبری هیتلر به دنبال فتح جهان بودند. برای راحتی، کشورها و روابط بین آن‌ها را به شکل گرافی nn راسی و mm یالی نشان می‌دهیم که راس‌ها نشان دهنده‌ی کشور‌ها و یال‌ها نشان دهنده‌ی همسایگی دو طرفه بین کشورها است.

در ابتدا کشور iiام قدرت aia_i را دارد و یکی از آن‌ها آلمان نازی است. هیتلر در جهت کشورگشایی هر بار می‌تواند یک کشور جدید که حداقل یکی از همسایه‌هایش فتح شده را انتخاب کند، و اگر قدرت آلمان نازی بیشتر اکید از آن بود، آن کشور را فتح کند. پس از فتح یک کشور، به اندازه‌ی قدرت آن کشور، به قدرت آلمان نازی اضافه می‌شود.

توضیح تصویر

سوالی که آن زمان فکر سیاست مداران را به خود درگیر کرده بود، این بود که آیا هیتلر می‌تواند موفق شود همه‌ی کشورها را فتح کند یا خیر؟ و اگر نمی‌تواند، حداقل چه مقدار باید قدرت آلمان نازی افزایش یابد تا بتواند به این هدف برسد؟ اما از آن‌جایی که هیتلر مخفی است و مکان اولیه آلمان نازی را نمی‌دانیم، شما باید به ازای هر کشور، این مقدار را محاسبه کنید!

ورودی🔗

در سطر اول ورودی، دو عدد nn و mm به ترتیب نشان‌دهنده‌ی تعداد کشورها و تعداد روابط همسایگی بین کشورها می‌آیند.

1n1933,n1m1945 1 \le n \le 1933, \quad\quad n-1 \le m \le 1945

در سطر دوم ورودی، اعداد a1,a2,,ana_1, a_2, \dots, a_n \, که قدرت کشورها را نشان می‌دهند، می‌آیند.

1ai109 1 \le a_i \le 10^9

در هر کدام از mm سطر بعدی، دو عدد vv و uu می‌آیند که نشان دهنده‌ی یالی بین راس vvام و راس uuام است.

1v,un,vu 1 \le v, u \le n, \quad\quad v \neq u

تضمین می‌شود گراف داده شده همبند باشد.

خروجی🔗

در تنها سطر خروجی، باید nn عدد با فاصله از هم چاپ کنید که عدد iiام حداقل مقداری است که باید به کشور iiام اضافه کنیم تا در صورتی که آلمان نازی این کشور باشد، بتواند همه‌ی کشورها را فتح کند. (ممکن است این مقدار 00 باشد.)

مثال‌ها🔗

ورودی نمونه ۱🔗

3 2
1 2 3
1 2
2 3
Plain text

خروجی نمونه ۱🔗

2 1 0
Plain text

توضیح تصویر

اگر مکان اولیه آلمان نازی:

  • کشور ۱ باشد و با قدرت 33 شروع به کار کند، ابتدا می تواند کشور ۲ را فتح کند تا قدرتش 55 شود. سپس می‌تواند کشور ۳ را فتح کند و به هدفش برسد. بنابراین باید حداقل 22 واحد به قدرتش اضافه کند.

  • کشور ۲ باشد و با قدرت 33 شروع به کار کند، ابتدا می تواند کشور ۱ را فتح کند تا قدرتش 44 شود. سپس می‌تواند کشور ۳ را فتح کند و به هدفش برسد. بنابراین باید حداقل 11 واحد به قدرتش اضافه کند.

  • کشور ۳ باشد و با قدرت 33 شروع به کار کند، ابتدا می تواند کشور ۲ را فتح کند تا قدرتش 55 شود. سپس می‌تواند کشور ۱ را فتح کند و به هدفش برسد.

می‌توان نشان داد اگر با قدرتی کمتر از این مقدار شروع کند، نمی‌تواند به هدفش برسد.

ورودی نمونه ۲🔗

7 10
16 1 32 256 4 128 64
2 6
6 7
1 2
3 7
5 4
7 5
6 2
4 2
4 6
6 3
Plain text

خروجی نمونه ۲🔗

112 112 33 0 61 12 29
Plain text

توضیح تصویر

اگر مکان اولیه آلمان نازی:

  • کشور ۱ باشد و با قدرت 128128 شروع به کار کند، ابتدا می‌تواند کشور ۲ را فتح کند تا قدرتش 129129 شود. سپس می‌تواند کشور ۶ را فتح کند تا قدرتش 257257 شود. اکنون می‌تواند به ترتیب کشورهای ۳، ۴، ۵ و ۷ را فتح کند و به هدفش برسد. بنابراین باید حداقل 112112 واحد به قدرتش اضافه کند.

  • کشور ۲ باشد و با قدرت 128128 شروع به کار کند، ابتدا می‌تواند کشور ۱ را فتح کند تا قدرتش 129129 شود. سپس همان روال کشور ۱ را می‌توان ادامه داد.

  • کشور ۳ باشد و با قدرت 6565 شروع به کار کند، ابتدا می‌تواند کشور ۷ را فتح کند تا قدرتش 129129 شود. اکنون می‌تواند به ترتیب کشور ۶، ۵، ۴، ۲ و ۱ را فتح کند و به هدفش برسد.

  • کشور ۴ باشد و با قدرت 256256 شروع به کار کند، می‌تواند به ترتیب کشورهای ۲، ۱، ۵، ۶، ۳ و ۷ را فتح کند و به هدفش برسد.

  • کشور ۵ باشد و با قدرت 6565 شروع به کار کند، ابتدا می‌تواند کشور ۷ را فتح کند تا قدرتش 129129 شود. سپس می‌تواند کشور ۶ را فتح کند تا قدرتش 257257 شود. سپس می‌تواند به ترتیب کشورهای ۴، ۳، ۲ و ۱ را فتح کند و به هدفش برسد.

  • کشور ۶ باشد و با قدرت 140140 شروع به کار کند، ابتدا می‌تواند به ترتیب کشورهای ۲، ۳، ۷، ۵ و ۱ را فتح کند تا قدرتش 257257 شود. در نهایت می‌تواند کشورهای ۴ را فتح کند و به هدفش برسد.

  • کشور ۷ باشد و با قدرت 9393 شروع به کار کند، ابتدا می‌تواند کشور ۵ را فتح کند تا قدرتش 9797 شود. سپس می‌تواند کشور ۳ را فتح کند تا قدرتش 129129 شود. سپس می‌تواند کشور ۶ را فتح کند تا قدرتش 257257 شود. در نهایت می‌تواند به ترتیب کشورهای ۴، ۲ و ۱ و به هدفش برسد.

می‌توان نشان داد اگر با قدرتی کمتر از این مقدار شروع کند، نمی‌تواند به هدفش برسد.