Reachable Pairs

문제

Consider an undirected graph with $NN$ nodes labeled $1\dots N1\backslash dots\; N$ and $MM$ edges ($1\le N\le 2\cdot {10}^5,0\le M\le 4\cdot {10}^{5}1\backslash le\; N\backslash le\; 2\backslash cdot\; 10^5,\; 0\backslash le\; M\backslash le\; 4\backslash cdot\; 10^5$). You're given a binary string $s_1{s}_2\dots s_{N}s\_1s\_2\backslash dots\; s\_N$. At time $tt$ for each $t\in [1,N]t\backslash in\; [1,N]$,

• If $s_t=0s\_t=0$, node $tt$ is removed from the graph.
• If $s_t=1s\_t=1$, node $tt$ is removed from the graph, and edges are added between every pair of neighbors that node $tt$ had just before removal.

Note that in both cases, when a node is removed from the graph all of its incident edges are removed as well.

Count the number of pairs of nodes that can reach each other via some sequence of edges just before each of timesteps $1\dots N1\backslash ldots\; N$.

입력

The first line contains $NN$ and $MM$.

The second line contains the bit string $ss$ of length $NN$.

The next $MM$ lines each contain two integers denoting an edge of the graph.

출력

$NN$ lines, the number of pairs before each timestep.

3 2
111
1 2
1 3

3
1
0

3 2
000
1 2
1 3

3
0
0

7 8
1101101
6 2
1 2
2 3
6 3
1 3
1 7
4 5
2 7

11
7
4
2
1
1
0