LCA oflayn (Asan)

İlkin olaraq, yalnız kökdən (nömrəsi $1$ olan düyün) ibarət bir ağac verilir. Aşağıdakı sorğulara cavab verməlisiniz:

• ADD $ab$ — düyün $b$-ni düyün $a$-ya birləşdirin (zəmanət verilir ki, düyün $a$ artıq mövcuddur).

• GET $ab$ — düyünlər $a$ və $b$ üçün LCA (Ən Aşağı Ortak Əcdad)-ı qaytarın.

Düyünlər $1$-dən $n$-ə qədər nömrələnmişdir. Hər zaman yalnız bir ağac mövcuddur.

Çıxış

Hər GET tipli sorğu üçün, uyğun cavabı bir tam ədəd kimi ayrıca sətrdə çap edin.