Mağaralar və tunellər#5285
Mars səthinə endikdən sonra alimlər tunellərlə birləşən qəribə bir mağara sistemi kəşf etdilər. Onlar bu sistemi idarə olunan robotlarla araşdırmağa başladılar. Məlum oldu ki, hər bir mağara cütlüyü arasında yalnız bir yol mövcuddur. Lakin alimlər tezliklə xüsusi bir problemlə qarşılaşdılar: bəzən mağaralarda zəif partlayışlar baş verir. Bu partlayışlar radioaktiv izotopların yayılmasına və mağaradakı radiasiya səviyyəsinin artmasına səbəb olur. Təəssüf ki, robotlar radiasiyaya dözümlü deyillər. Araşdırma məqsədilə isə onlar bir mağaradan digərinə köçməlidirlər. Buna görə alimlər hər mağaraya radiasiya səviyyəsini izləmək üçün sensorlar yerləşdirdilər. İndi robot hərəkət etdikdə, alimlər robotun üzləşəcəyi maksimum radiasiya səviyyəsini bilmək istəyirlər.
Ona görə də bu problemi həll edəcək proqramı yazmağı sizdən xahiş etdilər.
Birinci sətirdə (1 \leq N \leq 100\,000) — mağaraların sayı verilir. Növbəti N-1 sətrdə tunellər təsvir edilir. Hər sətirdə tunellə birləşən mağaraların nömrələrini göstərən iki tam ədəd — a_i və b_i (1 \leq a_i, b_i \leq N) verilir. Sonrakı sətirdə isə (1 \leq Q \leq 100\,000) — sorğuların sayı olan tam ədəd verilir. Sonra növbəti sətirdə hər biri "C U V" formatında olan sorğular verilir, burada — sorğunun tipini göstərən 'I' və ya 'G' simvoludur (tırnak işarələri yalnız aydınlıq üçün verilmişdir).
Əgər sorğu 'I' tipindədirsə, -ci mağaradakı radiasiya səviyyəsi qədər artır (1 \leq U \leq N, 0 \leq V \leq 10\,000). 'G' tipli sorğu üçün isə proqramınız və nömrəli mağaralar arasında bütün əvvəlki artımlardan ('I' sorğuları) sonra maksimum radiasiya səviyyəsini çap etməlidir (1 \leq U, V \leq N). Başlanğıcda bütün mağaralarda radiasiya səviyyəsi -dır və zaman keçdikcə heç vaxt azalırmır (çünki izotopların yarı ömrü müşahidə müddətindən qat-qat böyükdür).
Hər 'G' sorğusu üçün bir sətirdə yalnız uyğun yol üçün maksimum radiasiya səviyyəsini çap edin.
Nümunə 1