← 返回题目列表

AtCoder · past202005_e

E. 洒水器

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

分数: 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