Ümumi əcdad - 3
Asılmış ağac - dövrü olmayan istiqamətli qrafdır, burada hər bir zirvəyə yalnız bir kənar daxil olur, istisna isə istiqamətli ağacın kökü adlanan zirvədir. Kök zirvəyə heç bir kənar daxil olmur. Zirvənin atası, ona kənarın daxil olduğu zirvə adlanır (Wikipedia materiallarına əsasən).
Sizə bir neçə asılmış ağac verilib. Aşağıdakı əməliyyatları yerinə yetirməlisiniz:
0 u v - Verilən iki zirvə u və v üçün onların eyni ağacda olub-olmadığını yoxlayın. Əgər eyni ağacdadırsa, onların ən kiçik ümumi əcdadını tapın, əks halda 0 qaytarın.
1 u v - Ağaclardan birinin kökü u və digər ağacın istənilən zirvəsi v üçün kənar (v, u) əlavə edin. Bu əməliyyat nəticəsində iki ağac birləşəcək.
Bütün əməliyyatlar onlayn şəkildə yerinə yetirilməlidir, yəni növbəti sorğunu yalnız əvvəlkini yerinə yetirdikdən sonra öyrənə bilərsiniz.
Giriş verilənləri
Giriş faylının ilk sətirində n - ağaclardakı zirvələrin ümumi sayı (1 ≤ n ≤ 50000) verilir. Növbəti sətirdə başlanğıc konfiqurasiyada hər bir zirvənin əcdadı və ya əgər zirvə kökdürsə 0 olan n ədəd verilir. Sonra k - sorğuların sayı (1 ≤ k ≤ 100000) gəlir. Növbəti k sətirin hər biri üç tam ədəd ehtiva edir: sorğunun növü (0 - LCA axtarışı üçün və ya 1 - kənar əlavə etmək üçün) və iki ədəd x, y. Sorğuda iştirak edən zirvələri aşağıdakı düsturlarla hesablamaq olar: u = (x - 1 + ans) mod n + 1, v = (y - 1 + ans) mod n + 1, burada ans - sonuncu 0 tipli sorğunun cavabıdır.
Çıxış verilənləri
Hər bir 0 tipli sorğu üçün çıxış faylında ayrı sətirdə bir ədəd çıxarın - bu sorğunun cavabı.