Hamilton dövrü
Qraf Uilyam Hamilton dünya səyahətinə çıxmaq qərarına gəldi və bu səyahət zamanı Yer kürəsinin N ən böyük şəhərini ziyarət etmək istədi. Bütün şəhər cütləri arasında yollar mövcuddur. Bir şəhərdən digərinə gedən hər bir yola qraf Hamilton müəyyən bir ədəd (görkəmlilik) təyin edir ki, bu da 2 ədədinin qüvvətidir. Çünki bir yolun hər iki tərəfində mənzərələr fərqlidir, yolda bir istiqamətdə keçərkən görkəmlilik digər istiqamətdə keçərkən fərqlənir. Üstəlik, məlum oldu ki, bütün yolların görkəmliliyi fərqlidir. Qraf, bütün şəhərlərdən bir dəfə keçərək, eyni şəhərdə başlayıb bitən və maksimum ümumi görkəmliliyə malik olan qapalı bir marşrut seçmək istəyir.
Qraf Hamilton üçün optimal qapalı marşrutu müəyyən edən bir proqram yazın.
Giriş verilənləri
Birinci sətirdə N şəhərin sayı verilir (2 ≤ N ≤ 1000). Növbəti N sətirdə N ədəd verilir. Əgər i-ci sətirdəki j-ci ədəd c_ij bərabərdirsə, onda i şəhərindən j şəhərinə gedən yolun görkəmliliyi 2^cij bərabərdir. Bütün c_ij ədədləri fərqlidir və 0 ilə 10^6 daxil olmaqla diapazondadır. c_ii ədədləri həmişə -1 bərabərdir, bu da i şəhərindən özünə gedən və başqa bir şəhərdən keçməyən yolun mövcud olmadığını göstərir.
Çıxış verilənləri
Qraf Hamiltonun marşrutunun ən böyük görkəmliliyə malik olması üçün şəhərləri hansı ardıcıllıqla ziyarət etməli olduğunu göstərən bütün şəhərlərin nömrələrini çıxarın. Bu ardıcıllıqda hər bir şəhər yalnız bir dəfə görünməlidir, birindən başqa - qrafın marşrutuna başlayacağı şəhər. Bu şəhər marşrutun əvvəlində və sonunda iki dəfə görünməlidir. Əgər bir neçə optimal marşrut varsa, onlardan hər hansı birini çıxarmaq olar.