C. 小L的旅行
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

今天是周末！小 $$$\text{L}$$$ 决定去北京城区玩。

根据小 $$$\text{L}$$$ 的经验，北京城区有 $$$n$$$ 个景点，一共有 $$$m$$$ 条单向边将这些景点连接起来，第 $$$i$$$ 条边从第 $$$u_i$$$ 出发到达第 $$$v_i$$$ 个景点，经过一条边需要耗费 $$$1$$$ 分钟的时间。而小 $$$\text{L}$$$ 此时在第 $$$1$$$ 个景点。

小 $$$\text{L}$$$ 觉得这样出行太慢啦！所以小 $$$\text{L}$$$ 找住在房山区的小 $$$\text{P}$$$ 要了一张《北京传送门地图》。具体来说，第 $$$i$$$ 个景点具有 $$$a_i$$$ 的魔力值，如果存在一个景点 $$$j$$$ 满足 $$$a_i$$$ $$$\rm{and}$$$ $$$a_j = a_j$$$（$$$\rm{and}$$$ 指按位与运算，详见本题的Notes部分），那么就存在一个从第 $$$i$$$ 个景点通向第 $$$j$$$ 个景点的单向传送门，她就可以花费 $$$1$$$ 分钟的时间，直接从 $$$i$$$ 到达 $$$j$$$。

如此庞大的交通网络让小 $$$\text{L}$$$ 看得眼花缭乱，而小 $$$\text{P}$$$ 这周末去合肥旅游了，所以她决定直接来问你：如果她决定去第 $$$i$$$ 个景点，最少需要花费多少分钟？你需要对于所有 $$$i\in[1,n]$$$ 都回答一遍。

Input

第一行输入两个整数 $$$n,m$$$ ($$$1\leq n\leq 2 \times 10^5,1\leq m\leq 3 \times 10^5$$$)，代表景点数量和边的数量。

第二行输入 $$$n$$$ 个整数 $$$a_1,a_2, \cdots ,a_n$$$ ($$$0\leq a_i \lt 2^{20}$$$)，代表各个景点的魔力值。

接下来的 $$$m$$$ 行，每行输入两个整数 $$$u_i,v_i$$$ ($$$1\leq u_i,v_i \leq n$$$)，代表第 $$$i$$$ 条边是从第 $$$u_i$$$ 个到第 $$$v_i$$$ 个景点的单向边。

Output

输出 $$$n$$$ 行，第 $$$i$$$ 行表示从第 $$$1$$$ 个景点到达第 $$$i$$$ 个景点最少需要多少分钟。如果到达不了第 $$$i$$$ 个节点，则第 $$$i$$$ 行输出 $$$-1$$$。

Example
Input
5 2
5 4 2 3 7
1 4
2 3
Output
0
1
2
1
-1
Note

按位与运算：

对于两个二进制数的按位与运算，只有当他们同一位的数字同为1时才为1，否则取0。相当于数学与的同真为真，在C/C++中对应的运算符号是 $$$\&$$$ 。例如：$$$(1010)_2\ \rm{and}\ (1100)_2=(1000)_2$$$ 。