P7457 [CERC2018] The Bridge on the River Kawaii

**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/)[ The Bridge on the River Kawaii](https://contest.felk.cvut.cz/18cerc/solved/bridge.pdf)** 在一个遥远的，叫做 Midsommer 的地方，有一条叫做 delta 的小河。河里流的是深紫色的酸，所以不可能在那里游泳。这条河周围有一些小岛，并且有桥连接它们。每座桥都有一个危险系数，表示通过这座桥有多危险。危险系数越高，通过这座桥就越危险。 一位叫做 Richard Hradecki 的侦探兼悬疑小说作家经常需要通过这些桥来追查案件。在所有可能的路径中，他更倾向于选择最安全的一条，也就是这条路径上经过桥的最大危险系数越低越好。 为了规划路线，Richard 经常让你为他找从一个岛到他要调查的岛的最安全路线。为了满足他的需求，你需要连续处理以下三种事件： - 当地人在两座岛屿之间建了一座新桥； - 一只酸性的并且毛茸茸的大粉熊 Lug 出现了，并摧毁了一座桥； - Richard 要求你找两个岛屿之间的最安全路线。

无

无

$2≤N≤10^5,1≤Q≤10^5,0≤V≤10,0≤X,Y