25263번 - Stranded Far From Home 서브태스크다국어

문제

You just couldn’t leave it alone… You actually carried out the break-in, and initially everything worked out as planned. However, the communication with your assistant went terribly wrong.* Instead of returning safely to Lübeck, you are now stranded on a small island, and your submarine is out of fuel.

To return in time for the BOI award ceremony, you now have to get to the ferry on the other side of the island. However, the local population has strange traditions. Ties are very important to them, and every village has its own preferred tie color which might change over time.

A report from the internet tells you that different villages initially preferred different tie colors. Unfortunately, the report is quite outdated. Since then, every week exactly one village convinced a neighboring village to prefer the same tie color as them. (Two villages are neighbors if they are directly connected by a road.) However, this can only happen if there were at least as many people on the entire island who preferred the tie color of the first village as there were people who preferred the tie color of the second village. Enough time has passed so that all islanders now prefer the same tie color.

You are almost sure that the islanders won’t let you pass if you don’t wear a tie matching their preference. To get to the ferry, you therefore plan to wear a tie of every color that the islanders could prefer. However, wearing too many ties will make you look suspicious. Write a program that uses a description of the island to calculate which ties you have to wear.

* That was to be expected, right?

입력

The first line of the input contains two integers $N$ and $M$ where $N$ is the number of villages and $M$ is the number of roads on the island. The villages are numbered from 1ドル$ to $N$.

The next line contains $N$ integers $s_1, \dots , s_N$ where $s_i$ describes the number of inhabitants of village $i$.

Each of the following $M$ lines contains two integers $a$ and $b$ (1ドル ≤ a, b ≤ N,ドル $a \ne b$), meaning that there is a road between villages $a$ and $b$. All villages are connected to each other at least indirectly.

출력

Your program should output a string of length $N$ consisting of 0s and 1s. The $i$-th digit should be 1 if and only if it is possible that all islanders now prefer the tie color that village $i$ preferred initially.

제한

It always holds that 1ドル ≤ N ≤ 200,000円,ドル 0ドル ≤ M ≤ 200,000円,ドル and 1ドル ≤ s_i ≤ 10^9$.

서브태스크

힌트

The following picture shows the first example:

The first digit of the output is 1ドル$ since it is possible that all islanders now prefer the tie color that village 1ドル$ preferred initially. This could happen as follows: In the first week, village 1ドル$ convinces village 2ドル$ that their tie color is better. After that, there are four people who prefer the tie color of village 1ドル$. Therefore, village 1ドル$ can now convince village 3ドル$ of their tie color, and if afterwards village 3ドル$ convinces village 4ドル,ドル everybody prefers the tie color that village 1ドル$ preferred initially.

The last digit of the output is 0ドル$ since it is impossible that village 4ドル$ convinces anyone of their tie color. This is because village 4ドル$ is only connected to village 3ドル,ドル but village 3ドル$ has more inhabitants.

Note that the second example is a valid test case for the second subtask.