06758. USACO·可达点对 未做

考虑一个无向图，包含 $N$ 个结点，编号为 $1\dots N$，以及 $M$ 条边（$1\le N\le 2\cdot 10^5$，$0\le M\le 4\cdot 10^5$）。给定一个位串 $s_1{s}_2\dots s_N$。对于每一个 $t\in [1,N]$，在时刻 $t$ 时，

• 如果 $s_t=0$，则从图中移除结点 $t$。
• 如果 $s_t=1$，则从图中移除结点 $t$，并在结点 $t$ 被移除之前的每对邻居之间添加一条边。

注意在这两种情况下，当一个结点从图中被移除时它的所有相邻边也会被移除。

计算在每一个时刻 $1\dots N$ 之前，可以通过一组边相互到达的结点对数。

输入的第一行包含 $N$ 和 $M$。

第二行包含长为 $N$ 的位串 $s$。

以下 $M$ 行，每行包含两个整数，表示图中的一条边。

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

【样例解释】

• 测试点 7-8：所有 $s_i$ 均等于 $0$。

• 测试点 9-11：所有 $s_i$ 均等于 $1$。

• 测试点 12-23：没有额外限制。

【数据规模与约定】

• 测试点 4-6：$N\le 100$。

• 测试点 7-8：所有 $s_i$ 均等于 $0$。

• 测试点 9-11：所有 $s_i$ 均等于 $1$。

• 测试点 12-23：没有额外限制。

供题：Benjamin Qi