Ağac kodunun sındırılması
Tutaq ki, V = {1, 2, …, n} və E = {{u, v} | 1 ≤ u, v ≤ n}. Ağac T = (V, E) əlaqəli qrafdır və dəqiq olaraq n-1 kənar ehtiva edir. Məsələn, ağac T_1 aşağıdakı şəkildə göstərilmişdir.
Ağac T_1 üçün: V = {1,2,3,4,5,6,7}, E = {{4, 6}, {2, 6}, {6, 5}, {3, 5}, {5, 1}, {1, 7}}. Professor Minton ağacı kodlaşdırma üsulunu kəşf etdi. Ağacın kodu V dəstindən n - 2 ədəd ardıcıllığıdır. Məsələn, T_1 <6, 5, 6, 5, 1> ardıcıllığı ilə kodlaşdırıla bilər. Ardıcıllıqda bəzi ədədlər buraxıldıqda, bu ardıcıllıq pozulmuş hesab olunur. Buraxılmış ədədləri təmsil etmək üçün x simvolundan istifadə edəcəyik. Verilmiş ağac və pozulmuş ardıcıllığa əsasən buraxılmış ədədləri tapmaq lazımdır.
Giriş verilənləri
Birinci sətir testlərin sayını t ehtiva edir. İkinci sətir n dəyərini ehtiva edir. Üçüncü sətir ağacı təsvir edir və boşluqla ayrılmış 2n - 2 ədəd ehtiva edir. Birinci cüt ədəd birinci kənarı təyin edir; ikinci cüt - ikinci kənarı; və s. Dördüncü sətir n - 2 ədəd ardıcıllığını ehtiva edir, bunlardan bəziləri x simvolu ilə təmsil olunur ki, bu da onların olmadığını göstərir.
Çıxış verilənləri
Hər test üçün bir sətir olmaqla t sətir ehtiva edir. Hər sətir girişdə olduğu kimi buraxılmış ədədlərin ardıcıllığını ehtiva etməlidir.