Vahid Alt Ağaclar

Uniform ağacı, müəyyən bir səviyyədəki bütün düyünlərin eyni sayda uşağa malik olduğu ağac kimi təyin edilir. Bu, hər səviyyədəki uşaq sayını göstərən tam ədədlər siyahısı ilə təsvir edilə bilər. Məsələn, [2 3 5 0] siyahısı kökün 2 uşağa, hər kök uşağının 3 uşağa, hər nəvənin 5 uşağa malik olduğu və nəticələrin uşağı olmadığı bir ağacı təsvir edir.

Bu məsələdə, Alt ağac ağacın kökünü də daxil edən əlaqəli alt qraf kimi yenidən təyin edilir. Bu, Alt ağacın ənənəvi tərifindən bir qədər fərqlidir.

Ağacın təsviri verildikdə, həmin ağacın bütün unikal Uniform Alt ağaclarını tapın. Məsələn, burada bir ağac və onun bütün unikal uniform alt ağacları göstərilmişdir:

Giriş verilənləri

Girişdə bir neçə test halı olacaq. Hər bir test halı bir ağacdan ibarət olacaq və bir sətirdə təqdim olunacaq. Sətir uyğun açılış və bağlanış mötərizələrinin ardıcıllığı olacaq. Hər uyğun cüt bir düyünü təmsil edir və aradakı sətir onun uşaqlarını təmsil edir. Ağacda 4000 düyündən çox olmayacaq. Sətirdə boşluq və ya başqa simvollar olmayacaq. Giriş bir sətirdə tək 0 ilə bitəcək.

Çıxış verilənləri

Hər bir test halı üçün verilmiş ağacın hər bir unikal uniform alt ağacını tam ədədlər siyahısı kimi çıxarın, hər alt ağac (və beləliklə hər siyahı) bir sətirdə. Tam ədədlər arasında tək boşluq qoyun və başqa heç bir yerdə boşluq qoymayın. Siyahılar arasında və ya test halları arasında boş sətirlər çap etməyin. Verilmiş test halı üçün siyahıları birinci elementə, sonra ikinciyə, sonra üçüncüyə və s. görə sıralayın.