Yeni tövlələr#10415
Fermer Con inəklərinin bir-birinə çox yaxın olduqda tez-tez dalaşdıqlarını müşahidə edib, buna görə də onları bir-birindən uzaqlaşdırmaq üçün bir sıra yeni tövlələr tikmək istəyir.
Fermer Con yeni bir tövlə tikdikcə, onu artıq mövcud olan tövlələrdən biri ilə ən çoxu bir ikitərəfli cığırla birləşdirir. İnəklərin bir-birindən kifayət qədər uzaq yerləşdirildiyinə əmin olmaq üçün o, bəzən verilmiş tövlədən ondan əlçatan ən uzaq tövləyə qədər olan məsafəni müəyyən etmək istəyir (iki tövlə arasındakı məsafə — bir tövlədən digərinə çatmaq üçün keçilməli olan cığırların sayıdır).
Fermer Con cəmi sorğu edəcək, onların hər biri ya tikinti sorğusu, ya da məsafə sorğusu olacaq. Tikinti sorğusunda Fermer Con bir tövlə tikir və onu əvvəllər tikilmiş tövlələrdən ən çoxu biri ilə birləşdirir. Məsafə sorğusunda Fermer Con verilmiş tövlədən cığırlar ardıcıllığı ilə ondan əlçatan ən uzaq tövləyə qədər olan məsafəni soruşur. Sorğu edilən tövlənin artıq tikilmiş olduğu təmin edilir. Fermer Cona bütün sorğulara cavab verməkdə kömək edin.
Birinci sətirdə sorğuların sayını göstərən q~(1 \le q \le 10^5) tam ədədi verilir. Növbəti sətirdən hər biri B p və ya Q k formasında bir sorğu ehtiva edir. B p sorğusu tövləsi ilə birləşdirilən yeni bir tövlənin tikildiyini bildirir; əgər p = -1 olarsa, yeni tövlə heç bir digər tövlə ilə birləşdirilmir, əks halda — artıq tikilmiş tövlənin nömrəsidir. Q k sorğusu tövləsindən ondan əlçatan ən uzaq tövləyə qədər olan məsafəni tapmağı tələb edir. Tövlələr tikilmə ardıcıllığına görə -dən nömrələnir: tikilən ilk tövlənin nömrəsi , ikincisi — və beləliklə davam edir.
Hər məsafə sorğusu üçün cavabı ayrı sətirdə çap edin. Qeyd edin ki, heç bir digər tövlə ilə birləşdirilməmiş tövlə üçün cavab -a bərabərdir.
Nümunədəki giriş məlumatları aşağıdakı tövlə şəbəkəsinə uyğundur:
(1)
\
(2)---(4)
/
(3)-ci sorğuda nömrəli tövlə tikilir. -ci sorğuda nömrəli tövlədən ondan əlçatan ən uzaq tövləyə qədər olan məsafə soruşulur. nömrəli tövlə heç bir digər tövlə ilə birləşdirilmədiyi üçün cavab -dır. -cü sorğuda nömrəli tövlə ilə birləşdirilən nömrəli tövlə tikilir. -cü sorğuda nömrəli tövlə ilə birləşdirilən nömrəli tövlə tikilir. -ci sorğuda nömrəli tövlədən ondan əlçatan ən uzaq tövləyə qədər olan məsafə soruşulur. Bu halda ən uzaq tövlə məsafəsində yerləşən nömrəli tövlədir. -cı sorğuda nömrəli tövlə ilə birləşdirilən nömrəli tövlə tikilir. -ci sorğuda nömrəli tövlədən ondan əlçatan ən uzaq tövləyə qədər olan məsafə soruşulur. Üç tövlənin, yəni , və -ün hamısı ondan məsafəsində yerləşir, buna görə də cavab -dir.
Nümunə 1