← 返回题目列表

AtCoder · typical90_ce

083. 彩色图 (★6)

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

配点:6 点

問題文

N 頂点 M 给出的是边为纯连接的单无向图。图的顶点分别被 1 减去 N 编号至。 i 第几条边双向连接了边界 a_i 和 按字典顺序比较 b_i 。

10^9 有不同的颜色,每种颜色都有 它们的编号最大为 1 减去 10^9 。 最初所有顶点都是彩色的 它涂有 1 。

下面表格的查询是 您将获得 Q 件,请按顺序处理。 给出了

  • 整数 x, y 。电流峰值 输出 x 的颜色编号并 颜色 x 和所有相邻顶点 用 y 重新绘制。

制約

  • 1 \leq N \leq 200000
  • N - 1 \leq M \leq \mathrm{min}(\frac{N(N - 1)}{2}, 200000)
  • 1 \leq a_i, b_i \leq N
  • 1 \leq Q \leq 200000
  • 1 \leq x_i \leq N
  • 1 \leq y_i \leq 10^9
  • 给定的图是一个简单的图
  • 给定的图形已连接
  • 所有输入均以整数形式给出

小课题·得点

这个问题可以分解为若干小课题,如果所有小课题的测试用例都正确,则被视为“完成了此小课题”。
提交的源码得分为已正确回答的小课题分数之和。

  1. (2 点): N, Q \leq 2000
  2. (4分):没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

N M
a_1 b_1
\vdots
a_M b_M
Q
x_1 y_1
\vdots
x_Q y_Q

出力

对每个查询的答案求和。 按顺序输出 Q 行。


入力例 1

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

出力例 1

1
1
3
2
5

每个查询执行以下操作: 在第

  • 1 个查询中,顶点 4 色号 输出 1 后,顶点 1, 4 颜色 2 更改为
  • 2 个查询中,顶点 3 色号 输出 1 后,顶点 1, 2, 3 颜色 3 更改为
  • 3 个查询中,顶点 2 色号 输出 3 后,顶点 1, 2, 3 颜色 4 更改为
  • 4 个查询中,顶点 4 色号 输出 2 后,顶点 1, 4 颜色 5 更改为
  • 5 个查询中,顶点 1 色号 输出 5 后,顶点 1, 2, 3, 4 颜色 6 更改为

入力例 2

10 20
1 3
7 8
5 8
2 3
7 10
6 7
4 7
9 5
6 5
2 9
4 2
5 7
3 10
4 8
1 8
10 8
5 3
9 1
7 3
2 1
10
3 5
2 2
8 9
5 3
8 2
3 9
7 1
7 1
8 4
6 8

出力例 2

1
5
1
9
3
3
9
1
1
1