E - スプリンクラー 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 7 点

注意

この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

1,2,3,\ldots,N の番号がついた N 個の頂点と 1,2,3,\ldots,M の番号がついた M 本の無向辺からなる無向グラフが与えられます。 辺 i は頂点 u_i と v_i を双方向につないでいます。

それぞれの頂点には色を塗ることが可能で、はじめ頂点 i は色 c_i で塗られています(この問題において、色は 1 以上 10^5 以下の整数で表されます)。

それぞれの頂点にはスプリンクラーが設置されています。 頂点 i にあるスプリンクラーを起動すると、頂点 i に隣接する全ての頂点の色がスプリンクラー起動時点の頂点 i の色で塗り替えられます。

以下の形式で与えられる Q 個のクエリ s_1, s_2, \ldots, s_Q を順番に処理してください。

  • 頂点 x の現在の色を出力する。その後、頂点 x にあるスプリンクラーを起動する。1 x という形式で与えられる。
  • 頂点 x の現在の色を出力する。その後、頂点 x の色を 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 行目では i 番目のクエリで指定された頂点 x の現在の色を出力せよ。

入力例 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 でそれぞれ塗られています。
  • 1 番目のクエリにより、頂点 2 に隣接する全ての頂点が色 10 に塗り替えられます。これにより、頂点 1,2,3 は全て 10 で塗られている状態になります。
  • 2 番目のクエリにより、頂点 1 の色が色 20 に上書きされます。
  • 3 番目のクエリにより、頂点 1 に隣接する全ての頂点が色 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

Score : 7 points

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is an undirected graph with N vertices numbered 1,2,3,\ldots,N and M edges numbered 1,2,3,\ldots,M. Edge i connects Vertex u_i and v_i bidirectionally.

Each vertex can be painted in a color. Initially, Vertex i is painted in Color c_i. (In this problem, colors are represented by integers from 1 through 10^5.)

Each vertex has a sprinkler on it. When the sprinkler at Vertex i is activated, it will repaint all the vertices adjacent to Vertex i in the color of Vertex i when it is activated.

Process Q queries s_1, s_2, \ldots, s_Q in order, which will be given in the formats below:

  • Print the current color of Vertex x, and then activate the sprinkler on Vertex x. This query is given in the format 1 x.
  • Print the current color of Vertex x, and then overwrite the color of Vertex x to y. This query is given in the format 2 x y.

Constraints

  • All values in input are integers.
  • 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 is a string in one of the following formats:
    • 1 x (1 \leq x \leq N)
    • 2 x y (1 \leq x \leq N, 1 \leq y \leq 10^{5})
  • The given graph contains no multiple edges or self-loops.

Input

Input is given from Standard Input in the following format:

N M Q
u_1 v_1
\vdots
u_M v_M
c_1 c_2 \cdots c_N
s_1
\vdots
s_Q

Output

Print Q lines. The i-th line should contain the color of the vertex x specified in the i-th query.

Sample Input 1

3 2 3
1 2
2 3
5 10 15
1 2
2 1 20
1 1

Sample Output 1

10
10
20
  • Initially, Vertex 1, 2, and 3 are painted in Color 5, 10, and 15, respectively.
  • The first query repaints all the vertices adjacent to Vertex 2 in Color 10. After that, Vertex 1, 2 and 3 are all painted in Color 10.
  • The second query overwrites the color of Vertex 1 to Color 20.
  • The third query repaints all the vertices adjacent to Vertex 2 in Color 20.

Sample Input 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

Sample Output 2

18
19
37
29
8
24
18
25
46
10
18
42
23
4
17
8
24
7
25
16