Міст через річку Кавайї#9748
У далекій землі під назвою Мідсоммер розташована чарівна маленька річкова дельта. По річці тече густа пурпурна кислота, тому плавати в ній неможливо. У дельті знаходяться кілька островів, деякі з яких з'єднані мостами. Кожен міст має рівень небезпеки, який вказує, наскільки небезпечно перетинати цей міст — чим вище значення, тим небезпечніший перехід.
Детектив — а заодно і письменник детективних романів — на ім'я Ріхард Градецький часто подорожує між островами в ході своїх розслідувань. Серед усіх можливих маршрутів Ріхард віддає перевагу найбезпечнішому, тобто такому шляху, у якого максимальний рівень небезпеки серед усіх мостів на маршруті мінімальний.
Щоб допомогти Ріхарду у його переміщеннях, Вам необхідно обробляти три типи подій:
Між двома островами місцеві жителі побудували новий міст.
З'являється гігантський рожевий пухнастий кислотний ведмідь на ім'я Луг і руйнує міст.
Ріхард запитує про найбезпечніший шлях між двома островами.
Перший рядок містить два цілих числа та q~(2 \le n \le 10^5, 1 \le q \le 10^5) — кількість островів та кількість подій відповідно. Острови нумеруються від до n - 1.
Кожен з наступних рядків описує одну подію та містить три або чотири цілі числа, інтерпретовані наступним чином:
0~x~y~v: між островами та побудований міст з рівнем небезпеки v~(0 \le v < 10);
: міст між островами та зруйнований;
: Ріхард цікавиться найбезпечнішим маршрутом між островами та .
Для всіх подій виконуються наступні умови:
та y~(0 \le x, y < n, x \ne y) — допустимі та різні номери островів;
У будь-який момент між двома островами існує не більше одного мосту;
Кожен видалюваний міст на момент видалення дійсно існує.
Для кожного запиту типу виведіть в окремому рядку рівень небезпеки найнебезпечнішого мосту на найбезпечнішому шляху між островами та . Якщо шляху між ними не існує, виведіть .
Приклад 1
Приклад 2