Хваталın t-şərtlərində Hamilton dövrünün axtarışı

Verilmiş qrafda N zirvə var və bu qraf Xvatala teoreminin şərtini ödəyir. Yəni, zirvələrin dərəcələrinin sıralanmış ardıcıllığında hər hansı k < n/2 üçün ya d_k > k, ya da d_{n - k} ≥ n-k şərti doğrudur. Sizin vəzifəniz Hamilton dövrü tapmaqdır.

Giriş verilənləri

Giriş faylının ilk sətirində qrafın zirvələrinin sayı olan tam ədəd N (3 ≤ N ≤ 100) verilib. Sonrakı N sətirdə qonşuluq matrisi təqdim olunub. Bu matrisi simmetrikdir və diaqonalda həmişə sıfırlar var, buna görə də i-ci sətirdə i-1 simvol - sıfırlar və birlər yazılıb. Əgər i-ci sətirin j-ci simvolu birə bərabərdirsə, deməli i və j zirvələri arasında kənar mövcuddur.

Çıxış verilənləri

Hamilton dövründə zirvələrin nömrələrini göstərən N ədədindən ibarət bir sıra çıxarın.

Nümunələr