← 返回题目列表

AtCoder · abc411_f

I. 收缩

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

给你一个无向图 G_0 与 N 顶点和 M 边缘。 的顶点和边 G_0 被编号为顶点 1, 2, \ldots, N 和边缘 1, 2, \ldots, M分别是,和 边缘 i (1\leq i\leq M) 连接顶点 U_i 和 V_i.

高桥有一张图 G 和 N 件编号为件 1, 2, \ldots, N.
最初, G=G_0,以及一块 i (1\leq i\leq N) 放置在顶点上 i of G.

他现在将表演 Q 操作按顺序进行。 的 i第次操作 (1\leq i\leq Q) 给出一个整数 X_i 之间 1 和 M,包含在内,并执行以下操作:

In G,如果件 U_{X_i} 和 V_{X_i} 被放置在不同的顶点上并且 存在一个边缘 e (上 G) 在它们之间创建一个图表 G' 通过收缩该边缘。 在这种情况下,如果创建了自环,请将其删除,如果存在多边,则将其替换为简单边。
然后,放置在由边连接的两个顶点上的所有棋子 e in G 通过收缩放置在新生成的顶点上 e in G'。 放置在其他顶点上的碎片 G 放置在相应的顶点上 G'。 最后,设置这个结果 G' 作为新的 G.
如果件 U_{X_i} 和 V_{X_i} 放置在同一顶点上,或者如果它们放置的顶点没有通过边连接,则不执行任何操作。

对于每个操作 i=1,2,\ldots, Q,输出中的边数 G 之后 i第次操作。

边缘收缩 连接顶点的边的边收缩 u 和 v 是合并顶点的操作 u,v 进入一个顶点。 更准确地说,通过对 G 是指执行以下操作的结果 G:
  • 添加新顶点 w to G.
  • 对于每个顶点 x 除 u,v in G,当且仅当至少有一条边连接 u 和 x 或边缘连接 v 和 x 存在,添加一条边连接 w 和 x.
  • 删除顶点 u,v 并删除连接顶点的所有边 u 和 v,以及连接顶点的所有边 u 或顶点 v 与其他顶点。

约束

  • 2\leq N\leq 3\times 10^5
  • 1\leq M\leq 3\times 10^5
  • 1\leq U_i<V_i\leq N
  • (U_i,V_i)\neq (U_j,V_j) if i\neq j.
  • 1\leq Q\leq 3\times 10^5
  • 1\leq X_i\leq M
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M
Q
X_1 X_2 \ldots X_Q

输出

输出 Q 行。 上 i第行 (1\leq i\leq Q),输出中的边数 G 之后 i第次操作。


示例输入 1

7 7
1 2
1 3
2 3
1 4
1 5
2 5
6 7
5
1 2 3 1 5

示例输出 1

4
3
3
3
2

最初, G 如下图所示。带圆圈的数字代表带有这些数字的棋子。

在 1st操作,我们收缩顶点之间的边,其中碎片 放置了 1 和 2 (下左图)。
操作后, G 变成如下右图所示,特别是边数为 4。 请注意,自环已被删除,多边已被简单边替换。

在 2第一个操作,我们收缩顶点之间的边,其中碎片 放置了 1 和 3 。
操作后, G 变成如下左图所示,边数变成 3.
在 3rd操作,自件 2 和 3 放置在同一顶点上, G 保持不变,边数保持不变 3.
在 4第次操作也是如此,因为件 1 和 2 放置在同一顶点上, G 保持不变,边数保持不变 3.
在 5第次操作,我们收缩顶点之间的边,其中碎片 1 和 5 。
操作后, G 变为如下右图所示,边数变为 2.

因此,输出 4,3,3,3,2 按此顺序,用换行符分隔。