이벤추얼 저니

LCR은 정말 대단한 존재이다.

그렇게 생각하며 비행기에 앉아 바다를 바라보는 Rikka는 환상적인 여정을 만끽한다. 불은 결코 일어나지 않았다. 동료들과 이 여정을 나누는 것도 흥미로울 테고, 또 다른 여행도 매력적이다.

하지만 무엇보다도 집이 최고다.

Rikka는 JR 노선을 이용해 여행한다. 총 $n$개의 역이 있고, 그 사이에 $m$개의 공용 양방향 철도 노선이 건설되어 있다. 각 역은 JR 서일본 또는 JR 동일본 중 하나에 속한다. JR 서일본과 JR 동일본은 각각 자신이 소유한 모든 역을 연결하는 전용 철도를 운영한다.

Rikka는 몇 장의 승차권과 두 종류의 특별 패스, 즉 JR 서일본용 ICOCA와 JR 동일본용 Suica를 가지고 있다. 그녀는 매번 승차권을 지불하고 다음 중 하나를 수행한다.

1. 공용 철도 노선을 통해 한 종점에서 다른 종점으로 이동한다.
2. 특별 패스 중 하나를 사용해 현재 역과 같은 소유주를 가진 임의의 역으로 이동한다. 패스는 여러 번 사용할 수 있다.

Rikka는 각 출발 역에 대해, 다른 모든 역에 도달하기 위해 지불해야 하는 최소 승차권 수의 합을 알고 싶어 한다.

첫 번째 줄에는 두 정수 $n, m (1 \leq n \leq 10^5, 0 \leq m \leq 10^5)$가 주어지며, 이는 역의 수와 공용 철도의 수이다.

다음 줄에는 $n$개의 정수 $A\_i (A\_i \in \{0,1\}, i = 1, 2, \dots, n)$가 공백으로 구분되어 주어지며, 각 역의 소유주를 나타낸다. $A\_i = 0$이면 역 $i$는 JR 서일본에 속하고, 그렇지 않으면 JR 동일본에 속한다.

다음 $m$개의 줄에는 모든 공용 철도가 주어지며, 각 줄에는 두 정수 $u, v (1 \leq u, v \leq n, u \neq v)$가 주어져 $u$와 $v$를 연결하는 양방향 철도를 나타낸다. 같은 두 역을 연결하는 공용 철도는 두 개 이상 존재하지 않으며, Rikka는 모든 역 쌍 사이를 이동할 수 있음이 보장된다. 전용 철도는 입력에 직접 주어지지 않으며, Rikka는 공용 철도만 이용하는 대신 패스를 사용해야 할 수도 있다.

한 줄에 $n$개의 정수를 공백으로 구분하여 출력한다. $i$번째 정수는 $\sum\_{j=1}^n D(i, j)$이며, 여기서 $D(u, v)$는 $u$에서 $v$로 이동하는 데 필요한 최소 승차권 수이다.