当前没有测试数据。

游走距离

题目描述

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

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

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

输入格式

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

第二行包含$n$个正整数$val_{1}$,$val_{2}$,$\ldots$,$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