P11674 [USACO25JAN] Reachable Pairs G

考虑一个无向图，包含 $N$ 个结点，编号为 $1\dots 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$ 被移除之前的每对邻居之间添加一条边。 注意在这两种情况下，当一个结点从图中被移除时它的所有相邻边也会被移除。 计算在每一个时刻 $1\ldots N$ 之前，可以通过一组边相互到达的结点对数。

输入的第一行包含 $N$ 和 $M$。 第二行包含长为 $N$ 的位串 $s$。 以下 $M$ 行，每行包含两个整数，表示图中的一条边。

输出 $N$ 行，为每一个时刻之前所求的对数。

样例 1 解释： 在移除之前，所有结点对之间都可以相互到达。结点 $1$ 被移除后，结点 $2$ 和 $3$ 之间添加了一条边，因此它们仍然可以相互到达。 样例 2 解释： 在移除之前，所有结点对之间都可以相互到达。结点 $1$ 被移除后，结点 $2$ 和 $3$ 之间不再可以相互到达。 - 测试点 $4\sim 6$：$N\le 100$。 - 测试点 $7\sim 8$：所有 $s_i$ 均等于 $0$。 - 测试点 $9\sim 11$：所有 $s_i$ 均等于 $1$。 - 测试点 $12\sim 23$：没有额外限制。