Kawayi çayı üzərində körpü#9748
Uzaq bir diyarda Midsommer adlanan gözəl bir çay deltası yerləşir. Çayda tünd bənövşəyi turşu axır, buna görə də orada üzmək mümkün deyil. Deltada bir neçə ada var, bəzi ada cütlükləri körpülərlə birləşib. Hər bir körpü təhlükə səviyyəsinə malikdir, bu səviyyə körpüdən keçməyin nə qədər təhlükəli olduğunu göstərir — dəyər nə qədər yüksəkdirsə, keçid də bir o qədər təhlükəlidir.
Dedektiv və eyni zamanda dedektiv romanlar yazarı olan Rixard Hradetski araşdırmaları əsnasında adalar arasında tez-tez səyahət edir. Bütün mümkün marşrutlar arasında Rixard ən təhlükəsizini, yəni marşrutdakı bütün körpüləri arasında təhlükə səviyyəsi maksimal olanlardan ən kiçiyini seçir.
Rixarda kömək etmək üçün sizin üç növ hadisəni emal etməyiniz lazımdır:
İki ada arasında yerli sakinlər yeni bir körpü tikiblər.
Lug adlı nəhəng çəhrayı, tüklü turşu ayısı meydana gəlir və körpünü dağıdır.
Rixard iki ada arasında ən təhlükəsiz marşrutla maraqlanır.
Birinci sətir adaların sayı və hadisələrin sayını ifadə edən iki tam ədəd və q~(2 \le n \le 10^5, 1 \le q \le 10^5) ehtiva edir. Adalar -dan n - 1-ə qədər nömrələnib.
Sonrakı sətirin hər biri bir hadisəni təsvir edir və belə şəkildə təhlil olunan üç və ya dörd tam ədəd ehtiva edir:
0~x~y~v: adalar və arasında təhlükə səviyyəsi v~(0 \le v < 10) olan körpü quruldu;
: adalar və arasında olan körpü dağıldı;
: Rixard adalar və arasında ən təhlükəsiz marşrutla maraqlanır.
Bütün hadisələr üçün aşağıdakı şərtlər yerinə yetirilir:
və y~(0 \le x, y < n, x \ne y) — adaların fərqli və uyğun nömrələridir;
Hər hansı bir anda iki ada arasında ən çox bir körpü mövcuddur;
Hər bir silinən körpü silmə anında həqiqətən mövcuddur.
Hər bir tipli sorğu üçün ayrı bir sətirdə adalar və arasında ən təhlükəsiz marşrutdakı ən təhlükəli körpünün təhlükə səviyyəsini yazın. Onların arasında bir yol mövcud deyilsə, çıxış verin.
Nümunə 1
Nümunə 2