分数: 7 点
警告
2020 年 6 月 6 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
给定一个无向图 N 顶点编号 1,2,3,\ldots,N 和 M 边编号 1,2,3,\ldots,M。 边缘 i 连接顶点 u_i 和 v_i 双向。
每个顶点都可以涂上一种颜色。最初,顶点 i 涂有颜色 c_i。 (在这个问题中,颜色由整数表示 1 通过 10^5.)
每个顶点上都有一个洒水器。当洒水器到达顶点时 i 被激活,它将重新绘制与Vertex相邻的所有顶点 i 顶点颜色 i 当它被激活时。
流程 Q 查询 s_1, s_2, \ldots, s_Q 按顺序给出,格式如下:
- 打印顶点的当前颜色 x,然后激活 Vertex 上的洒水器 x。该查询以以下格式给出
1 x. - 打印顶点的当前颜色 x,然后覆盖Vertex的颜色 x to y。该查询以以下格式给出
2 x y.
约束
- 输入中的所有值都是整数。
- 1 \leq N,Q \leq 200
- 0 \leq M \leq N(N-1)/2
- 1 \leq u_i, v_i\leq N
- 1 \leq c_i\leq 10^5
- s_i 是采用以下格式之一的字符串:
1 x(1 \leq x \leq N)2 x y(1 \leq x \leq N, 1 \leq y \leq 10^{5})
- 给定的图不包含多重边或自环。
输入
输入由标准输入按以下格式给出:
N M Q u_1 v_1 \vdots u_M v_M c_1 c_2 \cdots c_N s_1 \vdots s_Q
输出
打印 Q 行。的 i第行应包含顶点的颜色 x 中指定 i第一个查询。
示例输入 1
3 2 3 1 2 2 3 5 10 15 1 2 2 1 20 1 1
示例输出 1
10 10 20
- 最初,顶点 1, 2,和 3 涂有颜色 5, 10,和 15。
- 第一个查询重新绘制与 Vertex 相邻的所有顶点 2 颜色 10。之后,顶点 1, 2 和 3 全部涂有颜色 10.
- 第二个查询覆盖顶点的颜色 1 到颜色 20.
- 第三个查询重新绘制与 Vertex 相邻的所有顶点 2 颜色 20.
示例输入 2
30 10 20 11 13 30 14 6 4 7 23 30 8 17 4 6 23 24 18 26 25 9 3 18 4 36 46 28 16 34 19 37 23 25 7 24 16 17 41 24 38 6 29 10 33 38 25 47 8 13 8 42 40 2 1 9 1 8 1 9 2 20 24 2 26 18 1 20 1 26 2 24 31 1 4 2 21 27 1 25 1 29 2 10 14 2 2 19 2 15 36 2 28 6 2 13 5 1 12 1 11 2 14 43
示例输出 2
18 19 37 29 8 24 18 25 46 10 18 42 23 4 17 8 24 7 25 16