LCA oflayn

Əvvəlcə yalnız kök (nömrəsi 1 olan zirvə) olan bir ağac var. Sizdən aşağıdakı sorğulara cavab vermək tələb olunur:

• ADD a b - b zirvəsini a zirvəsinə bağlayın (zirvə a-nın artıq mövcud olduğu təmin edilir).

• GET a b - a və b zirvələrinin Ən Aşağı Ümumi Əcdadını (LCA) qaytarın.

Bütün zirvə nömrələri 1-dən n-ə qədərdir. Hər zaman bir ağacımız var.

Giriş məlumatları

Birinci sətirdə sorğuların sayı k verilir. Sonrakı k sətir isə sorğuları ehtiva edir. Hər bir sorğu növünün sayı 500000-i keçmədiyi təmin edilir.

Çıxış məlumatları

Hər bir GET tipli sorğu üçün uyğun cavabı bir tam ədəd olaraq ayrıca sətirdə çıxarın.