#P8393. [BalticOI 2022 Day2] Stranded Far From Home

[BalticOI 2022 Day2] Stranded Far From Home

题目描述

你就是不能放任不管……实际上你进行了闯入行动,并且最初所有事情就像计划一样进行。然而,你和你的助手之间的通讯情况变得十分糟糕(这是符合预期的,不是吗?)你没有安全返回吕贝克,而是被困在一个小岛上,并且你的潜艇没有燃料了。

为了及时返回参加 BOI 的颁奖仪式,你现在必须去岛的另一边坐船。然而,当地居民有着奇怪的传统。领带对他们来说非常重要,每个村庄都有自己喜欢的领带颜色,并且这个颜色可能会随着时间的推移而改变。

一份互联网上的报告显示,不同的村庄最初喜欢不同的领带颜色。不幸的是,这份报告已经相当过时了。从那时起,每个星期都有恰好一个村庄说服一个相邻的村庄喜欢和他们一样的领带颜色(如果两个村庄有公路直接相连,它们就是相邻的)。然而,只有当整个岛上喜欢第一个村庄的领带颜色不比喜欢第二个村庄的领带颜色的人少时,这种情况才会发生。足够长的时间过去了,所以现在所有的岛民都喜欢同样的领带颜色。

你基本可以肯定,如果你不戴符合他们喜好的领带,岛民就不会让你通过。因此,为了去渡口,你计划戴上岛民可能喜欢的每种颜色的领带。然而,戴太多的领带会让你看起来很可疑。编写一个程序,使用对岛屿的描述来计算你必须戴哪些领带。

输入格式

第一行包含两个整数 nnmmnn 表示村庄的个数,mm 表示岛上道路的条数。村庄从 11nn 编号。

接下来一行包含 nn 个整数 s1,,sns_1,\dots,s_nsis_i 表示村庄 ii 的居民数。

接下来 mm 行,每行两个整数 aab(1a,bn,ab)b(1\le a,b\le n,a\neq b),表示村庄 aabb 之间有一条道路。所有村庄通过道路直接或间接相连。

输出格式

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

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

提示

【样例解释】

样例 #1 解释:

【数据范围】

对于所有数据,满足 1n2×1051\le n\le 2\times 10^50m2×1050\le m \le 2\times 10^51si1091 \le s_ i\le 10^9