P8393 [BalticOI 2022] Stranded Far From Home (Day2)

你就是不能放任不管……实际上你进行了闯入行动，并且最初所有事情就像计划一样进行。然而，你和你的助手之间的通讯情况变得十分糟糕（这是符合预期的，不是吗？）你没有安全返回吕贝克，而是被困在一个小岛上，并且你的潜艇没有燃料了。 为了及时返回参加 BOI 的颁奖仪式，你现在必须去岛的另一边坐船。然而，当地居民有着奇怪的传统。领带对他们来说非常重要，每个村庄都有自己喜欢的领带颜色，并且这个颜色可能会随着时间的推移而改变。 一份互联网上的报告显示，不同的村庄最初喜欢不同的领带颜色。不幸的是，这份报告已经相当过时了。从那时起，每个星期都有恰好一个村庄说服一个相邻的村庄喜欢和他们一样的领带颜色（如果两个村庄有公路直接相连，它们就是相邻的）。然而，只有当整个岛上喜欢第一个村庄的领带颜色不比喜欢第二个村庄的领带颜色的人少时，这种情况才会发生。足够长的时间过去了，所以现在所有的岛民都喜欢同样的领带颜色。 你基本可以肯定，如果你不戴符合他们喜好的领带，岛民就不会让你通过。因此，为了去渡口，你计划戴上岛民可能喜欢的每种颜色的领带。然而，戴太多的领带会让你看起来很可疑。编写一个程序，使用对岛屿的描述来计算你必须戴哪些领带。

第一行包含两个整数 $n$，$m$。$n$ 表示村庄的个数，$m$ 表示岛上道路的条数。村庄从 $1$ 到 $n$ 编号。 接下来一行包含 $n$ 个整数 $s_1,\dots,s_n$，$s_i$ 表示村庄 $i$ 的居民数。 接下来 $m$ 行，每行两个整数 $a$，$b(1\le a,b\le n,a\neq b)$，表示村庄 $a$ 和 $b$ 之间有一条道路。所有村庄通过道路直接或间接相连。

输出一个长度为 $n$ 的 $01$ 字符串。第 $i$ 位为 $1$ 当且仅当有可能所有的岛民现在都喜欢村庄 $i$ 最初喜欢的领带颜色。

【样例解释】 样例 #1 解释：  【数据范围】 * 子任务 1（10 分）：$N,M\leq2000$； * 子任务 2（10 分）：$s_1\geq s_2\geq\dots\geq s_n$ 且对于 $i=2\sim n$，有且仅有一个 $j$ 满足 $j$ 与 $i$ 相连； * 子任务 3（15 分）：$i,j$ 直接相连当且仅当 $|i-j|=1$； * 子任务 4（30 分）：有且仅有不超过 $10$ 种不同的 $s_i$； * 子任务 5（35 分）：无特殊限制。 对于所有数据，满足 $1\le n\le 2\times 10^5$，$0\le m \le 2\times 10^5$，$1 \le s_ i\le 10^9$。