你本以为能顺利离开……你确实实施了闯入计划，起初一切都按计划进行。然而，与助手的联络出了大问题*。你没能安全回到吕贝克，而是被困在一个小岛上，潜水艇也没油了。
为了能及时赶上 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$ 的字符串，由 $0$ 和 $1$ 组成。第 $i$ 位数字为 $1$ 当且仅当所有岛民现在偏好村庄 $i$ 最初偏好的领带颜色是有可能的。
数据范围
始终满足 $1 \le N \le 200\,000$，$0 \le M \le 200\,000$，且 $1 \le s_i \le 10^9$。
- 子任务 1（10 分）：$N \le 2\,000$ 且 $M \le 2\,000$。
- 子任务 2（10 分）：$s_1 \ge \dots \ge s_N$，且每个 $b > 1$ 的村庄都恰好与一个 $a < b$ 的村庄直接相连。
- 子任务 3（15 分）：村庄 $a$ 和 $b$ 直接相连当且仅当 $|a - b| = 1$。
- 子任务 4（30 分）：居民人数最多有 $10$ 种不同的取值。
- 子任务 5（35 分）：无附加限制。
样例
样例输入 1
4 4 2 2 4 3 1 2 1 3 2 3 3 4
样例输出 1
1110
样例输入 2
4 3 4 2 2 1 1 2 3 2 4 1
样例输出 2
1110
说明
下图展示了第一个样例：
输出的第一位是 $1$，因为所有岛民现在偏好村庄 $1$ 最初偏好的领带颜色是有可能的。这可以通过以下方式实现：第一周，村庄 $1$ 说服村庄 $2$ 他们的领带颜色更好。此后，共有四个人偏好村庄 $1$ 的领带颜色。因此，村庄 $1$ 现在可以向村庄 $3$ 推广他们的领带颜色，如果之后村庄 $3$ 再说服村庄 $4$，那么所有人都会偏好村庄 $1$ 最初偏好的领带颜色。
输出的最后一位是 $0$，因为村庄 $4$ 不可能说服任何人改用他们的领带颜色。这是因为村庄 $4$ 只与村庄 $3$ 相连，但村庄 $3$ 的居民人数更多。
注意，第二个样例是子任务 2 的一个有效测试用例。
- 那是意料之中的，对吧？