도달 가능한 쌍

무방향 그래프에 $1$부터 $N$까지 번호가 붙은 정점 $N$개와 간선 $M$개가 있다 ($1\le N\le 2\cdot 10^5$, $0\le M\le 4\cdot 10^5$). 이진 문자열 $s_1s_2\dots s_N$이 주어진다. $t\in [1,N]$인 각 시각 $t$에 대해 다음 연산을 수행한다.

• $s_t=0$이면 정점 $t$를 그래프에서 제거한다.
• $s_t=1$이면 정점 $t$를 그래프에서 제거하고, 제거 직전에 정점 $t$와 인접해 있던 정점들 중 임의의 두 정점 사이에 간선을 추가한다.

두 경우 모두 정점을 제거하면 그 정점에 연결된 간선도 함께 사라진다.

각 시각 $t$ 직전의 그래프에서 간선을 따라 서로 도달할 수 있는 정점 쌍의 개수를 구한다.

첫째 줄에 $N$과 $M$이 주어진다.

둘째 줄에 길이가 $N$인 이진 문자열 $s$가 주어진다.

이후 $M$개의 줄에 각각 간선의 양 끝점을 나타내는 정수 두 개가 주어진다.

$N$개의 줄을 출력한다. $t$번째 줄에는 시각 $t$ 직전에 서로 도달할 수 있는 정점 쌍의 개수를 출력한다.