Dynamic Graph Connectivity with Extra Edge Additions

You are given an undirected graph with \(N\) nodes labeled from \(1\) to \(N\) and \(M\) edges. In addition, you are given a bit string \(s = s_1s_2\dots s_N\). The process runs in \(N\) time steps. At time \(t\) (\(1 \le t \le N\)), the following operation is performed on node \(t\):

• If \(s_t = 0\), then remove node \(t\) from the graph. (When a node is removed, all its incident edges are removed.)
• If \(s_t = 1\), then before removing node \(t\), add an edge between every pair of its neighbors that are still in the graph, and then remove \(t\) (along with its incident edges).

After each time step \(t\), only nodes \(t+1, t+2, \dots, N\) remain in the graph. In the remaining graph the following edges exist:

• Every original edge connecting two nodes both in \(\{t+1,\dots,N\}\).
• For every node \(i\) with \(s_i = 1\) (and \(i \le t\)), an extra edge was added between every pair \(u,v\) of its neighbors at time \(i\). Note that at time \(i\) the neighbors of \(i\) are exactly those nodes \(j\) with \(j>i\) such that there is an edge \((i, j)\) in the original graph.

Your task is to compute, for each time step \(t = 1, 2, \dots, N\), the number of unordered pairs of remaining nodes that are in the same connected component. In other words, if the remaining nodes induce connected components of sizes \(c_1,c_2,\dots,c_k\), then the answer for that time step is \(\sum_{i=1}^k \binom{c_i}{2}\).

Note: All formulas must be rendered in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(N\) and \(M\) (\(1 \le N \le 2\cdot10^5\), \(0 \le M \le 4\cdot10^5\)).

The second line contains a bit string of length \(N\): \(s_1s_2\dots s_N\), consisting only of characters '0' and '1'.

The next \(M\) lines each contain two integers \(u\) and \(v\) (\(1 \le u, v \le N\), \(u \neq v\)), representing an undirected edge between nodes \(u\) and \(v\). There are no duplicate edges.

outputFormat

Output \(N\) lines. The \(t\)-th line should contain a single integer representing the number of unordered pairs of nodes (among nodes \(t+1, t+2, \dots, N\)) that are in the same connected component after processing time step \(t\). (If there is only one or no node, output 0.)

sample

3 2
101
1 2
2 3

1
0
0