You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

考虑一个无向图，包含 $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$ 行，为每一个时刻之前所求的对数。

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

提示

样例 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$：没有额外限制。