Yeni anbarlar
Fermer Con, inəklərinin çox yaxın olduqda tez-tez dalaşdığını gördü və onları bərabər şəkildə yerləşdirmək üçün yeni anbarlar tikmək qərarına gəldi.
Con hər dəfə yeni bir anbar tikəndə, onu mövcud anbarlardan ən çox biri ilə bir ikitərəfli yolla birləşdirir. İnəklərin bir-birindən kifayət qədər uzaq məsafədə yerləşdirildiyinə əmin olmaq üçün, Con bəzən müəyyən bir anbardan ona çata bilən ən uzaq anbardan olan məsafəni müəyyən etmək istəyir (iki anbar arasındakı məsafə, birindən digərinə keçmək üçün keçilməli olan yolların sayıdır).
Con ümumilikdə q sorğu təqdim edəcək, hər biri "tikmək" və ya "məsafə" formasında olacaq. "Tikmək" sorğusu üçün Con bir anbar tikir və onu ən çox bir tikilmiş anbarla birləşdirir. "Məsafə" sorğusu üçün Con sizdən müəyyən bir anbardan ona çata bilən ən uzaq anbardan olan məsafəni soruşur. Soruşulan anbarın artıq tikildiyi təmin edilir. Zəhmət olmasa, Con-a bu sorğuların hamısına cavab verməyə kömək edin.
Giriş məlumatları
Birinci sətirdə tam ədəd q (1 ≤ q ≤ 10^5) verilir. Növbəti q sətirin hər biri bir sorğu ehtiva edir. Hər bir sorğu "B p" və ya "Q k" formasındadır, bu da sizə anbardan p və ya k üçün ən uzaq məsafəni tikmək və ya hesablamaq lazım olduğunu göstərir. Əgər p = −1 olarsa, yeni anbar artıq tikilmiş anbarlardan heç biri ilə birləşdirilməyəcək. Əks halda, p artıq tikilmiş anbarın nömrəsidir. Anbarlar 1-dən başlayaraq nömrələnir, belə ki, ilk tikilmiş anbar 1, ikinci 2 və s. olacaq.
Çıxış məlumatları
Hər "məsafə" sorğusu üçün bir sətir çıxarın. Qeyd edək ki, digər anbarlarla birləşdirilməmiş anbarın ən uzaq məsafəsi 0-dır.
Nümunə
Nümunə giriş aşağıdakı anbar şəbəkəsinə uyğundur:
(1)
\
(2)---(4)
/
(3)Sorğu 1-də biz 1 nömrəli anbarı tikirik. Sorğu 2-də biz 1-dən ən uzaq birləşdirilmiş anbardan olan məsafəni soruşuruq. 1 nömrəli anbar digər anbarlarla birləşdirilmədiyi üçün cavab 0. Sorğu 3-də biz 2 nömrəli anbarı tikirik və onu 1 nömrəli anbarla birləşdiririk. Sorğu 4-də biz 3 nömrəli anbarı tikirik və onu 2 nömrəli anbarla birləşdiririk. Sorğu 5-də biz 3-dən ən uzaq birləşdirilmiş anbardan olan məsafəni soruşuruq. Bu halda, ən uzaq olan 1 nömrəli anbardır və məsafə 2 vahiddir. Sorğu 6-da biz 4 nömrəli anbarı tikirik və onu 2 nömrəli anbarla birləşdiririk. Sorğu 7-də biz 2-dən ən uzaq birləşdirilmiş anbardan olan məsafəni soruşuruq. Bütün üç anbar 1, 3, 4 məsafədə 1-dir, buna görə cavab 1.