LCA oflayn (Asan)

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

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

• GET $ab$ — $a$ və $b$ zirvələrinin LCA-sını (ən yaxın ortaq əcdadını) qaytar.

Zirvələr $1$-dən $n$-ə qədər nömrələnmişdir. Hər zaman bir ağacımız var.

Giriş verilənləri

Birinci sətirdə $k$ ədədi var — sorğuların sayı. Növbəti $k$ sətir sorğuları ehtiva edir. Hər bir tipdən olan sorğuların sayı $1000$-i keçməyəcəyi təmin edilir.

Çıxış verilənləri

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

Nümunələr