Sətirlər ağacda#2925
Verilmiş ağacda, yəni dövrləri olmayan əlaqəli qrafda hər bir kənar kiçik latın hərfi ilə işarələnmişdir. İstənilən iki zirvə arasında sadə yol (heç bir zirvəni bir dəfədən artıq ziyarət etməyən, ağacın kənarlarından keçən bir yol) vardır və bu yol yeganədir. Həmin yolun üzərindəki kənarların üzərindəki hərflər ardıcıllıqla oxunaraq, bu yol üçün bir sətir təyin olunur. Yol istənilən ucundan başlana bilər.
Sizə bir sətri verilir. Ağacda elə bir sadə yol varmı ki, onun kənar etiketlərini ardıcıl oxuduqda bu sətri əldə edək?
Sətrin uzunluğu və ağacın ölçüsü 3\cdot 10^5-dən böyük deyil.
Birinci sətirdə sətri verilir. İkinci sətirdə ağacın zirvələrinin sayı verilir. Sonrakı n-1 sətirdə isə hər biri formatında olan bir kənarın təsviri verilir; burada və ağacın zirvələri, isə bu ikisi arasındakı kənarın üzərindəki hərfdir.
Əgər belə bir yol varsa, birinci sətirdə çap edin, əks halda çap edin.
Əgər yol mövcuddursa, növbəti sətirdə sözügedən yolun başladığı və bitdiyi zirvələrin nömrələrini çap edin.
Nümunə 1