Hamilton dövrü#1680
Qraf Uilyam Hamilton Yer üzündəki ən böyük şəhəri ziyarət etməyə qərar verdi. Hər iki şəhər cütünü birləşdirən yollar mövcuddur. Hər yolun möhtəşəmlik dəyəri var, bu dəyər -nin qüvvəti şəklində olur. Yolun möhtəşəmlik dəyəri hər istiqamətə görə fərqli ola bilər və bütün yol möhtəşəmlik dəyərləri fərqlidir. Qraf, hər bir şəhərə yalnız bir dəfə baş çəkərək, başlanğıc və bitişi eyni şəhərdə olmaqla, ümumi möhtəşəmlik dəyəri maksimum olan qapalı marşrut seçmək istəyir.
Qraf Hamilton üçün ən optimal qapalı marşrutu müəyyənləşdirən proqram yazın.
Birinci sətirdə (2 \leq N \leq 1000) — şəhərlərin sayı verilir. Sonrakı sətrin hər birində tam ədəd var. -ci sətirdə -ci ədəd c_{ij}-dirsə, onda şəhər -dən şəhər -yə olan yolun möhtəşəmlik dəyəri 2^{c_{ij}}-dir. Bütün c_{ij}-lər fərqlidir və -dan 10^6-ya qədər (hər ikisi daxil) qiymətlər alır. c_{ii} həmişə -dir, yəni bir şəhərdən özünə yol yoxdur.
Qraf Hamiltonun marşrutunun maksimum möhtəşəmlik əldə edəcəyi şəhərlərin nömrələrinin ardıcıllığını çap edin. Hər şəhər bu ardıcıllıqda yalnız bir dəfə olmalıdır, başlanğıc şəhəri isə iki dəfə — əvvəl və sonda göstərilməlidir. Əgər bir neçə optimal marşrut varsa, onlardan istənilən birini çap edə bilərsiniz.
Nümunə 1