+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
در گذشتهای نه چندان دور $n$ کشور داشتیم که یکی از آنها آلمان نازی بود و به رهبری هیتلر به دنبال فتح جهان بودند.
برای راحتی، کشورها و روابط بین آنها را به شکل گرافی $n$ راسی و $m$ یالی نشان میدهیم که راسها نشان دهندهی کشورها و یالها نشان دهندهی همسایگی دو طرفه بین کشورها است.
در ابتدا کشور $i$ام قدرت $a_i$ را دارد و یکی از آنها آلمان نازی است. هیتلر در جهت کشورگشایی هر بار میتواند یک کشور جدید که حداقل یکی از همسایههایش فتح شده را انتخاب کند، و اگر قدرت آلمان نازی بیشتر اکید از آن بود، آن کشور را فتح کند. پس از فتح یک کشور، به اندازهی قدرت آن کشور، به قدرت آلمان نازی اضافه میشود.
![توضیح تصویر](https://quera.org/qbox/view/SxQxcNTjBc/Hitler.png)
سوالی که آن زمان فکر سیاست مداران را به خود درگیر کرده بود، این بود که آیا هیتلر میتواند موفق شود همهی کشورها را فتح کند یا خیر؟ و اگر نمیتواند، حداقل چه مقدار باید قدرت آلمان نازی افزایش یابد تا بتواند به این هدف برسد؟ اما از آنجایی که هیتلر مخفی است و مکان اولیه آلمان نازی را نمیدانیم، شما باید به ازای هر کشور، این مقدار را محاسبه کنید!
# ورودی
در سطر اول ورودی، دو عدد $n$ و $m$ به ترتیب نشاندهندهی تعداد کشورها و تعداد روابط همسایگی بین کشورها میآیند.
$$ 1 \le n \le 1933, \quad\quad n-1 \le m \le 1945 $$
در سطر دوم ورودی، اعداد
$a_1, a_2, \dots, a_n \,$
که قدرت کشورها را نشان میدهند، میآیند.
$$ 1 \le a_i \le 10^9 $$
در هر کدام از $m$ سطر بعدی، دو عدد $v$ و $u$ میآیند که نشان دهندهی یالی بین راس $v$ام و راس $u$ام است.
$$ 1 \le v, u \le n, \quad\quad v \neq u $$
**تضمین میشود گراف داده شده همبند باشد.**
# خروجی
در تنها سطر خروجی، باید $n$ عدد با فاصله از هم چاپ کنید که عدد $i$ام حداقل مقداری است که باید به کشور $i$ام **اضافه** کنیم تا در صورتی که آلمان نازی این کشور باشد، بتواند همهی کشورها را فتح کند. (ممکن است این مقدار $0$ باشد.)
# مثالها
## ورودی نمونه ۱
```
3 2
1 2 3
1 2
2 3
```
## خروجی نمونه ۱
```
2 1 0
```
![توضیح تصویر](https://quera.org/qbox/view/gSIOWsdI5Y/Samples-01.png)
اگر مکان اولیه آلمان نازی:
+ کشور ۱ باشد و با قدرت $3$ شروع به کار کند، ابتدا می تواند کشور ۲ را فتح کند تا قدرتش $5$ شود. سپس میتواند کشور ۳ را فتح کند و به هدفش برسد. بنابراین باید حداقل $2$ واحد به قدرتش اضافه کند.
+ کشور ۲ باشد و با قدرت $3$ شروع به کار کند، ابتدا می تواند کشور ۱ را فتح کند تا قدرتش $4$ شود. سپس میتواند کشور ۳ را فتح کند و به هدفش برسد. بنابراین باید حداقل $1$ واحد به قدرتش اضافه کند.
+ کشور ۳ باشد و با قدرت $3$ شروع به کار کند، ابتدا می تواند کشور ۲ را فتح کند تا قدرتش $5$ شود. سپس میتواند کشور ۱ را فتح کند و به هدفش برسد.
میتوان نشان داد اگر با قدرتی کمتر از این مقدار شروع کند، نمیتواند به هدفش برسد.
## ورودی نمونه ۲
```
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
```
## خروجی نمونه ۲
```
112 112 33 0 61 12 29
```
![توضیح تصویر](https://quera.org/qbox/view/udzh53sRyo/Samples-02.png)
اگر مکان اولیه آلمان نازی:
+ کشور ۱ باشد و با قدرت $128$ شروع به کار کند، ابتدا میتواند کشور ۲ را فتح کند تا قدرتش $129$ شود. سپس میتواند کشور ۶ را فتح کند تا قدرتش $257$ شود. اکنون میتواند به ترتیب کشورهای ۳، ۴، ۵ و ۷ را فتح کند و به هدفش برسد. بنابراین باید حداقل $112$ واحد به قدرتش اضافه کند.
+ کشور ۲ باشد و با قدرت $128$ شروع به کار کند، ابتدا میتواند کشور ۱ را فتح کند تا قدرتش $129$ شود. سپس همان روال کشور ۱ را میتوان ادامه داد.
+ کشور ۳ باشد و با قدرت $65$ شروع به کار کند، ابتدا میتواند کشور ۷ را فتح کند تا قدرتش $129$ شود. اکنون میتواند به ترتیب کشور ۶، ۵، ۴، ۲ و ۱ را فتح کند و به هدفش برسد.
+ کشور ۴ باشد و با قدرت $256$ شروع به کار کند، میتواند به ترتیب کشورهای ۲، ۱، ۵، ۶، ۳ و ۷ را فتح کند و به هدفش برسد.
+ کشور ۵ باشد و با قدرت $65$ شروع به کار کند، ابتدا میتواند کشور ۷ را فتح کند تا قدرتش $129$ شود. سپس میتواند کشور ۶ را فتح کند تا قدرتش $257$ شود. سپس میتواند به ترتیب کشورهای ۴، ۳، ۲ و ۱ را فتح کند و به هدفش برسد.
+ کشور ۶ باشد و با قدرت $140$ شروع به کار کند، ابتدا میتواند به ترتیب کشورهای ۲، ۳، ۷، ۵ و ۱ را فتح کند تا قدرتش $257$ شود. در نهایت میتواند کشورهای ۴ را فتح کند و به هدفش برسد.
+ کشور ۷ باشد و با قدرت $93$ شروع به کار کند، ابتدا میتواند کشور ۵ را فتح کند تا قدرتش $97$ شود. سپس میتواند کشور ۳ را فتح کند تا قدرتش $129$ شود. سپس میتواند کشور ۶ را فتح کند تا قدرتش $257$ شود. در نهایت میتواند به ترتیب کشورهای ۴، ۲ و ۱ و به هدفش برسد.
میتوان نشان داد اگر با قدرتی کمتر از این مقدار شروع کند، نمیتواند به هدفش برسد.
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.