Ağac kodunun sındırılması#2543
Qoy \textbf{V} = \{1, 2, \ldots, n\} və \textbf{E} = \{\{u, v\} \mid 1 \leq u, v \leq n\}. Bir ağac \textbf{T} = (V, E) dəqiq n - 1 ayridilən kənardan ibarət bağlı qrafdır. Məsələn, aşağıdakı şəkildə bir \textbf{T}_1 ağacı göstərilmişdir.
\textbf{T}_1-də \textbf{V} = \{1, 2, 3, 4, 5, 6, 7\}, \textbf{E} = \{\{4, 6\}, \{2, 6\}, \{6, 5\}, \{3, 5\}, \{5, 1\}, \{1, 7\}\}. Professor Minton bir ağacı kodlaşdırma üsulu tapıb. Ağacın kodu n - 2 ədədlik çoxluğundan olan rəqəmlər ardıcıllığıdır. Məsələn, \textbf{T}_1 ağacını <6, 5, 6, 5, 1> ardıcıllığı kimi kodlaşdırmaq olar. Əgər ardıcıllıqda bəzi ədədlər yoxdursa, həmin ardıcıllıq nöqsanlı sayılır. Əskik ədədin yerinə simvolu yazılır. Sizə bir ağac və nöqsanlı ardıcıllıq verilir, sizdən əskik olan ədədləri tapmaq tələb olunur.
Birinci sətirdə testlərin sayı verilir. İkinci sətirdə tam ədədi verilir. Üçüncü sətirdə ağac təsviri verilir və 2n - 2 ədəd boşluqla ayrılmış şəkildə yazılır. Hər iki ədəd bir kənarı təsvir edir. Birinci cüt birinci kənarı, ikinci cüt ikinci kənarı və s. göstərir. Dördüncü sətrdə n - 2 ədədlik ardıcıllıq verilir, ardıcıllığın bəzi elementləri isə hərfi ilə əvəzlənmişdir.
Hər test üçün bir sətrdə, daxil olan ardıcıllıqda göründüyü qayda ilə, əskik ədədləri ardıcıllıqla çap edin.
Nümunə 1