LCR 真是一个不可思议的人。
坐在飞机上，看着大海，Rikka 沉浸在这段奇妙的旅程中。火灾从未发生。与伙伴们分享这段经历一定很有趣，而另一段旅程也同样令人着迷。 但无论如何，家才是最好的。
她乘坐 JR 线旅行。总共有 $n$ 个车站，它们之间修建了 $m$ 条公共双向铁路。每个车站要么属于 JR West，要么属于 JR East。JR West 和 JR East 都有各自的私有铁路，连接着所有属于它们自己的车站。
Rikka 有一些通票和两种特殊通行证：用于 JR West 的 ICOCA 和用于 JR East 的 Suica。她每次支付一张通票，并执行以下操作之一：
- 通过公共铁路从一个终点站前往另一个终点站。
- 使用她的特殊通行证前往任何与当前车站所有者相同的车站。通行证可以多次使用。
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