AT_tkppc2016_j 次のお仕事 (New Game)

[problemUrl]: https://atcoder.jp/contests/tkppc2/tasks/tkppc2016_j ※この問題は時間制限が長いので、テストケースに入出力例を入れていません。 - - - - - - ひとまずゲーム作りを終えたjoisinoお姉ちゃんは、次のゲームの企画をすることになった。 そして、今度は地形が変わるマップでのアドベンチャーゲームを作ろうと思った。 以下joisinoお姉ちゃんの考えである。 このゲームではN個の街があって、それが$ N-1 $本の双方向に通行可能な道で互いに行き来できるようにつながっていることにしよう。 やっぱりアドベンチャーゲームなら街を巡ってゴールを目指すのがいいかな。 今回は遠回りすることは考えなくていいか。 それで、地形が変わるならやっぱり標高が重要かな。 標高が高い街を通るとレアなアイテムがもらえるとかどうだろう？ それなら旅で通る街の標高の最大値を求めればいいかな？ 地形を変えるならある街から道を$ c $本以下たどることでたどり着ける街すべての標高を変えるとかだね。 整理すると、この2つのイベントを処理すればいいってことだよね。 - イベント$ 1 $ 整数$ a,\ b,\ c $が与えられる。 街$ a $から$ b $本以下の道でたどり着ける街の標高が$ c $になる。 - イベント$ 2 $ 整数$ a,\ b $が与えられる。 街$ a $から街$ b $までの最短経路の街の標高の最大値に応じてアイテムがもらえる。 でも、これだとどれぐらいのアイテムをもらえるんだろう？ そこでjoisinoお姉ちゃんは、イベント2において最短経路の街の標高の最大値を求めるプログラムを書くことにした。

N/A

すべてのイベント2について、最短経路の街の標高の最大値を出力せよ。 - - - - - - ### 入力例1 ``` 5 5 3 2 5 2 6 1 2 2 3 3 5 3 4 2 1 5 0 1 4 1 7 2 5 2 0 1 3 1 2 2 4 1 0 ``` ### 出力例1 ``` 6 7 3 ``` - クエリ$ 1 $ : 街$ 1 $から街$ 5 $までの最短経路で通る街は$ 1,\ 2,\ 3,\ 5 $なので、それらの標高$ 3,\ 2,\ 5,\ 6 $の最大値$ 6 $を出力する。 - クエリ$ 2 $ : 街$ 4 $から$ 1 $本の道を通ってたどり着ける街は$ 4,\ 3 $なので、それらの標高を$ 7 $にする。 - クエリ$ 3 $ : 街$ 5 $から街$ 2 $までの最短経路で通る街は$ 5,\ 3,\ 2 $なので、それらの標高$ 6,\ 7,\ 2 $の最大値$ 7 $を出力する。 - クエリ$ 4 $ : 街$ 3 $から$ 1 $本の道を通ってたどり着ける街は$ 3,\ 2,\ 4,\ 5 $なので、それらの標高を$ 2 $にする。 - クエリ$ 5 $ : 街$ 4 $から街$ 1 $までの最短経路で通る街は$ 4,\ 3,\ 2,\ 1 $なので、それらの標高$ 2,\ 2,\ 2,\ 3 $の最大値$ 3 $を出力する。 - - - - - - ### 入力例2 ``` 10 10 78 87 33 57 93 49 45 17 56 44 1 2 2 3 1 4 1 5 4 6 3 7 6 8 3 9 6 10 2 2 2 0 1 1 2 59 1 7 1 96 2 7 8 0 2 3 4 0 2 10 4 0 1 8 2 45 1 3 3 24 2 2 1 0 2 6 9 0 ``` ### 出力例2 ``` 87 96 96 59 24 45 ```