Etibarlı təhlükəsizlik

Алиса və Bob gizli yeraltı obyektin xəritəsini əldə ediblər. Bu obyekt $n$ təhlükəsizlik bölməsindən və $m$ kimya laboratoriyasından ibarətdir, ikitərəfli tunellərlə birləşdirilib. Xəritə ağac şəklindədir: dəqiq n + m - 1 tunel var və heç bir dövr yoxdur. Təhlükəsizlik bölmələri $1$-dən $n$-ə qədər, kimya laboratoriyaları isə n + 1-dən n + m-ə qədər nömrələnib. Hər tunel bir təhlükəsizlik bölməsi ilə bir kimya laboratoriyasını birləşdirir; iki təhlükəsizlik bölməsi və ya iki kimya laboratoriyası arasında tunel yoxdur.

Əgər Alisa və ya Bob tutulsa, xəritəni iki hissəyə bölməyi planlaşdırıblar. Bunun üçün onlar ağacın Prüfer kodunu hesablayıblar. Alisa, orijinal kodda olduğu ardıcıllıqla $1$ və $n$ arasında olan bəzi rəqəmləri öz məlumat bazasında saxlayıb, Bob isə n + 1 və n + m arasında olan bəzi rəqəmləri eyni ardıcıllıqla öz məlumat bazasında saxlayıb.

$k$ zirvədən ibarət ağac üçün Prüfer kodu k - 2 tam ədəddən ibarət bir ardıcıllıqdır və bu ardıcıllıq $1$-dən $k$-ə qədər olan rəqəmlərdən ibarətdir. Kod aşağıdakı kimi qurulur: ən kiçik nömrəli yarpağı (dərəcəsi bir olan zirvə) tapın, onu ağacdan çıxarın, sonra onun yeganə qonşusunun nömrəsini çıxarın. Bu əməliyyatı daha k - 3 dəfə təkrarlayın, yalnız bir kənar qalana qədər. Çıxarılan zirvələrin k - 2 nömrəli ardıcıllığı Prüfer kodudur.

Alisa və Bob uğurla qayıdıblar və xəritənin orijinalını bərpa etmək üçün məlumatlarını birləşdirməyə hazırdırlar. Onlar ehtiyat nüsxə çıxararkən səhv edə bilərlər, bu da belə bir xəritənin mövcud olmadığını göstərə bilər. Alisa və Bobun topladıqları məlumatlara uyğun olaraq, xəritənin Prüfer kodunun alt ardıcıllıqları olan hər hansı bir mümkün obyekt xəritəsini bərpa etmək üçün köməyinizə ehtiyacları var.