Problem Description

You just cannot leave things alone... In fact, you carried out a break-in, and at first everything went according to plan. However, communication between you and your assistant became very poor (as expected, right?). You did not return safely to Lübeck; instead, you got stranded on a small island, and your submarine has run out of fuel.

To get back in time for the BOI award ceremony, you now have to travel to the other side of the island to take a boat. However, the locals have strange traditions. Neckties are very important to them: each village has its own favorite tie color, and this color may change over time.

An online report shows that different villages initially liked different tie colors. Unfortunately, the report is quite outdated. Since then, every week exactly one village has convinced one neighboring village to like the same tie color as theirs (two villages are neighbors if there is a road directly connecting them). However, this happens only when, over the entire island, the number of people who like the first village’s tie color is not smaller than the number of people who like the second village’s tie color. Enough time has passed, so now all islanders like the same tie color.

You are fairly sure that if you do not wear a tie matching their preferred color, the islanders will not let you pass. Therefore, to reach the ferry, you plan to wear ties of every color that the islanders could possibly like. However, wearing too many ties will make you look suspicious. Write a program that, given a description of the island, computes which ties you must wear.

Input Format

The first line contains two integers $n$ and $m$. $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$ is the number of residents in village $i$.

The next $m$ lines each contain two integers $a$ and $b$ $(1\le a,b\le n,\ a\neq b)$, meaning there is a road between villages $a$ and $b$. All villages are connected, directly or indirectly, via roads.

Output Format

Output a $01$ string of length $n$. The $i$-th character is $1$ if and only if it is possible that all islanders now like the tie color that village $i$ liked initially.

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

Hint

[Sample Explanation]

Sample #1 explanation:

[Constraints]

• Subtask 1 (10 points): $N,M\leq2000$.
• Subtask 2 (10 points): $s_1\geq s_2\geq\dots\geq s_n$, and for $i=2\sim n$, there exists exactly one $j$ such that $j$ is connected to $i$.
• Subtask 3 (15 points): $i$ and $j$ are directly connected if and only if $|i-j|=1$.
• Subtask 4 (30 points): there are at most $10$ distinct values among the $s_i$.
• Subtask 5 (35 points): no special restrictions.

For all testdata, $1\le n\le 2\times 10^5$, $0\le m \le 2\times 10^5$, $1 \le s_ i\le 10^9$.

Translated by ChatGPT 5