| ZCO 2025 |
|---|
| Закончено |
You have a secret. There are $$$N$$$ people in your class. $$$M$$$ pairs of these people are friends with each other. If person $$$A$$$ is friends with person $$$B$$$, person $$$B$$$ is also friends with person $$$A$$$.
Every night, you choose a set of people (which may be empty) to tell the secret to. Unfortunately, friends cannot keep a secret to themselves once you tell them. Thus, every morning, every person who knows the secret tells all of their friends the secret.
For each person $$$i$$$ there is an earliest day $$$D_i$$$ on which you are willing for the person to find out the secret. For some people, $$$D_i$$$ may be $$$-1$$$, meaning that you never want them to find out the secret. While satisfying these constraints, what is the earliest day that each person can find out the secret? If they can never find out the secret, output $$$-1$$$.
Please note that even if you are willing to tell a person $$$X$$$ the secret on day $$$D_X$$$, you may choose not to do so, as it may lead (directly or indirectly) to another person $$$Y$$$ learning of the secret before day $$$D_Y$$$.
The first line of input contains two space-separated integers $$$N$$$ and $$$M$$$. $$$N$$$ is the number of people in the class. $$$M$$$ is the number of pairs of friends in the class.
The second line of input contains $$$N$$$ space-separated integers. The $$$i$$$th of these integers represents $$$D_i$$$, the earliest day the $$$i$$$th person can find out the secret.
The following $$$M$$$ lines of input each contain two space-separated integers, $$$A_i$$$ and $$$B_i$$$. This means that person $$$A_i$$$ and $$$B_i$$$ are friends with each other.
Output $$$N$$$ space-separated integers. The $$$i$$$th of these integers should represent the earliest day the $$$i$$$th person can find out the secret, while ensuring that no person learns the secret before day $$$D_i$$$.
For all subtasks it is guaranteed that $$$1 \leq N \leq 2 \times 10^5$$$ and $$$0 \leq M \leq 2 \times 10^5$$$. Additionally, $$$1 \leq A_i \lt B_i \leq N$$$ for all $$$1 \leq i \leq M$$$. For all $$$1 \leq i \lt j \leq M$$$ it is guaranteed that at least $$$A_i \neq A_j$$$ or $$$B_i \neq B_j$$$ (or possibly both).
2 11 31 2
2 3
6 510 6 4 3 -1 61 22 61 63 44 6
10 9 7 8 -1 9
6 56 8 3 9 2 21 22 33 44 55 6
7 8 8 9 8 7
3 31 3 31 22 31 3
2 3 3
2 14 -11 2
-1 -1
| Название |
|---|


