LCR 真是一个不可思议的人。

坐在飞机上，看着大海，Rikka 沉浸在这段奇妙的旅程中。火灾从未发生。与伙伴们分享这段经历一定很有趣，而另一段旅程也同样令人着迷。 但无论如何，家才是最好的。

她乘坐 JR 线旅行。总共有 $n$ 个车站，它们之间修建了 $m$ 条公共双向铁路。每个车站要么属于 JR West，要么属于 JR East。JR West 和 JR East 都有各自的私有铁路，连接着所有属于它们自己的车站。

Rikka 有一些通票和两种特殊通行证：用于 JR West 的 ICOCA 和用于 JR East 的 Suica。她每次支付一张通票，并执行以下操作之一：

1. 通过公共铁路从一个终点站前往另一个终点站。
2. 使用她的特殊通行证前往任何与当前车站所有者相同的车站。通行证可以多次使用。

Rikka 想知道，对于每个起始车站，她到达其他所有可能车站所需支付的最小通票数量之和。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \le 10^5, 0 \le m \le 10^5$)，分别表示车站数量和公共铁路数量。

下一行包含 $n$ 个整数 $A_i$ ($A_i \in \{0, 1\}, i = 1, 2, \dots, n$)，以空格分隔，描述每个车站的所有者。如果 $A_i = 0$，则车站 $i$ 属于 JR West，反之则属于 JR East。

接下来的 $m$ 行描述了所有的公共铁路，每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \neq v$)，表示连接 $u$ 和 $v$ 的双向铁路。保证没有两条公共铁路连接同一对车站，且 Rikka 能够往返于任意两个车站之间。注意，私有铁路并未直接在输入中给出，Rikka 可能需要使用她的通行证，而不仅仅是通过公共铁路旅行。

输出格式

输出一行 $n$ 个整数，以空格分隔。第 $i$ 个整数是 $\sum_{j=1}^n D(i, j)$，其中 $D(u, v)$ 是从 $u$ 到 $v$ 旅行所需支付的最小通票数量。

样例

样例输入 1

3 2
1 0 0
1 2
1 3

样例输出 1

2 2 2

样例输入 2

5 3
1 0 1 0 1
1 2
2 3
4 5

样例输出 2

5 5 5 6 5