AT_past202005_e スプリンクラー

[problemUrl]: https://atcoder.jp/contests/past202005-open/tasks/past202005_e $ 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` という形式で与えられる。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ の現在の色を出力せよ。

### 注意 この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - 与えられる入力は全て整数 - $ 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}) $ - 与えられるグラフに多重辺や自己ループは存在しない ### Sample Explanation 1 \- はじめ、頂点 $ 1,2,3 $ は色 $ 5,10,15 $ でそれぞれ塗られています。 - $ 1 $ 番目のクエリにより、頂点 $ 2 $ に隣接する全ての頂点が色 $ 10 $ に塗り替えられます。これにより、頂点 $ 1,2,3 $ は全て $ 10 $ で塗られている状態になります。 - $ 2 $ 番目のクエリにより、頂点 $ 1 $ の色が色 $ 20 $ に上書きされます。 - $ 3 $ 番目のクエリにより、頂点 $ 1 $ に隣接する全ての頂点が色 $ 20 $ に上書きされます。