题目描述

在比特镇一共有 $n$ 个街区，编号依次为 $1$ 到 $n$，它们之间通过若干条单向道路连接。

比特镇的交通系统极具特色，除了 $m$ 条单向道路之外，每个街区还有一个编码 $val_i$，不同街区可能拥有相同的编码。如果 $val_i \ and \ val_j=val_j$，即 $val_i$ 在二进制下与 $val_j$ 做与运算等于 $val_j$，那么也会存在一条额外的从 $i$ 出发到 $j$ 的单向道路。

$\verb!Byteasar!$ 现在位于 $1$ 号街区，他想知道通过这些道路到达每一个街区最少需要多少时间。因为比特镇的交通十分发达，你可以认为通过每条道路都只需要 $1$ 单位时间。

输入格式

第一行包含两个正整数 $n,m$，表示街区的总数以及道路的总数。

第二行包含 $n$ 个正整数 $val_1,val_2,\cdots,val_n$ 分别表示每个街区的编码。

接下来 $m$ 行，每行包含两个正整数 $u_i,v_i$，表示一条单向道路，起点为 $u_i$，终点为 $v_i$。

输出格式

输出 $n$行，每行一个整数，其中第 $i$ 行输出到达第 $i$ 个街区的最少时间，如果无法到达则输出 $−1$。

样例输入输出

5 2
5 4 2 3 7
1 4
2 3

0
1
2
1
-1

说明/提示

对于 $100 \%$ 的数据，$1 \leqslant u_{i}, v_{i} \leqslant n, 1 \leqslant val_{i}<2^{20}$ 。