Ağaclar
İkili Axtarış Ağacı (BST), hər bir düyünün bir dəyəri olan və ağacın elə qurulduğu bir ikili ağacdır ki, hər hansı bir düyün üçün onun sol alt ağacındakı bütün dəyərlər həmin düyünün dəyərindən kiçik, sağ alt ağacındakı bütün dəyərlər isə böyükdür.
Müxtəlif tam ədədlər ardıcıllığından BST qurmaq üçün aşağıdakı prosedurdan istifadə olunur. İlk tam ədəd ağacın kökü olur. Sonra ardıcıllıqda ikinci tam ədəd nəzərə alınır. Əgər bu, kök düyünün dəyərindən kiçikdirsə, sol uşaq olur. Əks halda, sağ uşaq olur. Ardıcıllıqda sonrakı elementlər əvvəlki düyünlərlə müqayisəyə əsasən ya sola, ya da sağa hərəkət edir, kökdən başlayaraq ağacın aşağısına doğru irəliləyir. Yeni düyün, müəyyən istiqamətdə hərəkət edərkən itkin alt ağaca çatdıqda qismən qurulmuş ağaca (yarpaq kimi) daxil edilir.
Məsələn, [2, 1, 4, 3] ardıcıllığı ilə yaradılan BST, aşağıda göstərildiyi kimi, rəqəmlər daxil edildikcə qurulur.
Şəkil 1: BST-nin yaradılması
Şəkil 1-dəki ağac (d) iki başqa ardıcıllıqla da yaradıla bilər: [2, 4, 3, 1] və [2, 4, 1, 3].
Belə ardıcıllıqlar leksikoqrafik sıraya görə müqayisə edilə bilər, burada müqayisə soldan sağa doğru gedir və müvafiq mövqelərdəki elementlər öz ədədi dəyərləri ilə müqayisə edilir. [2, 1, 4, 3], [2, 4, 3, 1] və [2, 4, 1, 3] üçün nəticə belədir, ardıcıllıqlar arasında bu leksikoqrafik sıranı göstərmək üçün "<" işarəsindən istifadə olunur: [2, 1, 4, 3] < [2, 4, 1, 3] < [2, 4, 3, 1].
Şəkil 1-dəki ağac (d) üçün leksikoqrafik olaraq ən kiçik ardıcıllıq [2, 1, 4, 3]-dir.
Bir proqram yazın ki, ağacın təsvirini oxusun və həmin ağacı yaradan fərqli müsbət tam ədədlərin leksikoqrafik olaraq ən kiçik ardıcıllığını yaratsın. Qeyd edək ki, n düyünə malik ağac üçün bu ardıcıllıq 1 ilə n arasında olan rəqəmlərin bir permutasiyası olacaq.
Problemimizin girişi üçün ağacın quruluşunu (rekursiv olaraq) aşağıdakı kimi təsvir edirik:
Tək bir düyün (yarpaq) ağacdır:
()
Əgər TL və TR ağaclardırsa, onda aşağıdakılar da ağacdır:
(TL,)
(,TR)
(TL,TR)
Giriş verilənləri
Giriş bir sıra sətirlərdən ibarət olacaq. Hər bir sətir maksimum 250 simvoldan ibarət olacaq və yuxarıdakı tərifə uyğun olaraq bir ağacın spesifikasiyasını ehtiva edəcək (aralıq boşluqlar olmadan). Sıra tək bir düyündən ibarət olan () ağacı ilə bitəcək. Bu sətir işlənməməlidir.
Çıxış verilənləri
Çıxış hər bir giriş sətri üçün bir sətirdən ibarət olacaq. Hər bir sətir, ağacdakı düyünlərin sayına uyğun olaraq 1 ilə n arasında olan tam ədədlərin tələb olunan permutasiyasından ibarət olacaq və bu ədədlər tək boşluqlarla ayrılacaq.