配点: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
- 给定的图是一个简单的图
- 给定的图形已连接
- 所有输入均以整数形式给出
小课题·得点
这个问题可以分解为若干小课题,如果所有小课题的测试用例都正确,则被视为“完成了此小课题”。
提交的源码得分为已正确回答的小课题分数之和。
- (2 点): N, Q \leq 2000
- (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