k-cı əcdad
Bir qrafın p zirvəsi varsa və p - 1 kənar ilə əlaqəlidirsə, bu qrafa Dərə deyilir. Dərənin kökünü r ilə təyin edək. Əgər a zirvəsi r-dən l məsafəsindədirsə və b zirvəsi r-dən l + 1 məsafəsindədirsə və a ilə b birləşirsə, onda a zirvəsi b-nin əcdadı adlanır.
Eyni qaydada, əgər a zirvəsi r-dən l məsafəsindədirsə və b zirvəsi r-dən l + k məsafəsindədirsə və a-dan b-yə uzunluğu k olan bir yol varsa, onda a zirvəsi b-nin k-cı əcdadı adlanır.
Syuzen qraflarla oynamağı sevir və Dərə məlumat strukturu onun ən sevdiklərindən biridir. O, bir tapşırıq hazırlayıb və kimsənin onu həll edə biləcəyini bilmək istəyir. Bəzən o, yarpaq olan bir zirvə əlavə edir və ya silir. Sizin vəzifəniz hər an zirvənin k-cı əcdadını tapmaqdır.
Giriş məlumatları
Birinci sətir t (1 ≤ t ≤ 3) testlərin sayını ehtiva edir. Sonra t testlər gəlir. Hər testin birinci sətiri dərədəki zirvələrin sayı p (1 ≤ p ≤ 10^5) ehtiva edir. Sonrakı p sətirin hər biri iki tam ədəd x və y ehtiva edir ki, burada y x-in əcdadıdır. Əgər y 0-a bərabərdirsə, onda x dərənin köküdür (0 dərəyə aid deyil). Məlumdur ki, 1 ≤ x, y ≤ 10^5.
Növbəti sətir sorğuların sayını q (1 ≤ q ≤ 10^5) ehtiva edir. Sonrakı q sətirin hər biri bir sorğu ehtiva edir.
0 y x: x yeni yarpaq olaraq y əcdadı ilə əlavə olunur. x hələ dərədə deyil, y dərəyə aiddir.
1 x: yarpaq zirvə x dərədən silinir. x dərənin yarpağıdır.
2 x k: x-in k-cı (1 ≤ k ≤
10^5) əcdadını çıxarın. x dərədə olan bir zirvədir.
Çıxış məlumatları
Hər 2 tipli sorğu üçün x-in k-cı əcdadını çıxarın. Əgər k-cı əcdad mövcud deyilsə, 0 çıxarın. Əgər göstərilən zirvə mövcud deyilsə, 0 çıxarın.