AT_nupc2024_f Labeled Tree Distance

$ N $ 頂点の木 $ T $ が与えられます。辺 $ i $ は頂点 $ u_i $ と $ v_i $ を結んでいます。 最初、頂点 $ i $ は色 $ A_i $ で塗られています。 $ Q $ 個のクエリが与えられるので、順番に処理してください。クエリは次の $ 2 $ 種類のいずれかです。 - `1 k x`: 頂点 $ k $ を色 $ x $ で塗る - `2 y`: 色 $ y $ で塗られている $ 2 $ 頂点の距離の最大値を出力する ここで、 $ 2 $ 頂点 $ (u,v) $ の距離とは、 $ u $ と $ v $ を両端点とするパスに含まれる辺の本数です。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $ $ A_1\ A_2\ \ldots\ A_N $ $ Q $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ ここで、 $ \mathrm{query}_i $ は $ i $ 個目のクエリであり、以下のいずれかの形式で与えられます。 > $ 1 $ $ k $ $ x $ > $ 2 $ $ y $

2番目の形式のクエリの回数を $ q $ として $ q $ 行出力してください。 $ j (1\leq j \leq q) $ 行目では $ 2 $ 番目の形式のクエリのうち $ j $ 個目のものに対する答えを出力してください。

### Sample Explanation 1 最初、全てのマスが色 $ 1 $ で塗られています。このとき、色 $ 1 $ で塗られている $ 2 $ 頂点のうち、頂点 $ 1 $ と頂点 $ 3 $ の距離が最大となり、その距離は $ 2 $ です。 その後、頂点 $ 1 $ が色 $ 2 $ で塗られると、色 $ 1 $ で塗られている頂点では頂点 $ 2 $ と頂点 $ 3 $ の距離である $ 1 $ が最大となります。 ### Constraints - $ 2 \le N \le 10^5 $ - $ 1 \le u_i,v_i \le N $ - $ 1 \le A_i \le N $ - $ 1 \le Q \le 10^5 $ - $ 1 \le k \le N $ - $ 1 \le x \le N $ - $ 1 \le y \le N $ - クエリ`2 y`が与えられるとき、色 $ y $ で塗られている頂点が $ 2 $ つ以上存在する - 入力は全て整数である - 与えられるグラフは木である