Reachable Pairs

An undirected graph has $N$ nodes labeled $1$ to $N$ and $M$ edges ($1\le N\le 2\cdot 10^5$, $0\le M\le 4\cdot 10^5$). You are given a binary string $s_1s_2\dots s_N$. For each timestep $t$ from $1$ to $N$, do the following.

• If $s_t=0$, remove node $t$ from the graph.
• If $s_t=1$, remove node $t$ from the graph, and add an edge between every pair of neighbors that node $t$ had just before its removal.

In both cases, removing a node also removes all edges incident to it.

For each timestep $t$, count the pairs of nodes that can reach each other through a sequence of edges in the graph just before timestep $t$.

The first line contains $N$ and $M$.

The second line contains the binary string $s$ of length $N$.

Each of the next $M$ lines contains two integers, the endpoints of an edge.

Print $N$ lines. The $t$-th line contains the number of pairs of reachable nodes just before timestep $t$.