Birbaşa, mərkəzləşdirilmiş və tərs sıra
Bir verilənlər strukturu məsələsinin klassik nümunələrindən biri ikili ağacın düyünlərinin keçid qaydasıdır. Üç standart keçid variantı mövcuddur:
Düz: kök, sol alt ağac, sağ alt ağac ziyarət edilir;Mərkəzli: sol alt ağac, kök, sağ alt ağac ziyarət edilir;Tərs: sol alt ağac, sağ alt ağac, kök ziyarət edilir.
Şəkilə nəzər salaq:
Düz, mərkəzli və tərs keçid zamanı müvafiq olaraq ABCDEF, CBAEDF və CBEFDA əldə edirik. Məsələdə düz və mərkəzli keçidlər məlum olduqda, tərs keçid zamanı düyünlərin ardıcıllığını tapmaq tələb olunur.
Giriş məlumatları
Birinci sətir testlərin sayını c (c ≤ 2000) ehtiva edir. Hər bir növbəti sətir ayrı bir testdir və ikili ağacın düyünlərinin sayını n (1 ≤ n ≤ 52) və iki sətir S[1] və S[2] ehtiva edir ki, bunlar müvafiq olaraq ağacın düz və mərkəzli keçidlərini göstərir. Ağacın düyünləri a..z və A..Z çoxluqlarından fərqli simvollarla nömrələnmişdir. n, S[1] və S[2] boşluqla ayrılmışdır.
Çıxış məlumatları
Hər bir test üçün ağacın tərs keçid zamanı düyünlərin ardıcıllığını çıxış edin.