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 $NN$ and $MM$ where $NN$ is the number of villages and $MM$ is the number of roads on the island. The villages are numbered from $11$ to $NN$.

The next line contains $NN$ integers $s_1,\dots ,s_{N}s\_1,\; \backslash dots\; ,\; s\_N$ where $s_{i}s\_i$ describes the number of inhabitants of village $ii$.

Each of the following $MM$ lines contains two integers $aa$ and $bb$ (1 ≤ a, b ≤ N, $a\mathrm{\ne }ba\; \backslash ne\; b$), meaning that there is a road between villages $aa$ and $bb$. All villages are connected to each other at least indirectly.

출력

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

힌트

The following picture shows the first example:

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

The last digit of the output is $00$ since it is impossible that village $44$ convinces anyone of their tie color. This is because village $44$ is only connected to village $33$, but village $33$ has more inhabitants.

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

4 4
2 2 4 3
1 2
1 3
2 3
3 4

1110

4 3
4 2 2 1
1 2
3 2
4 1

1110