Tam qrafda Hamilton dövrü

Verilmiş qrafda N zirvə var və hər bir zirvənin dərəcəsi ən az N/2 qədərdir. Sizin vəzifəniz Hamilton dövrünü 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 ≤ 4000) verilir. Sonrakı N sətirdə qonşuluq matrisi təqdim olunur. Bu matrisi simmetrikdir və diaqonalda həmişə sıfırlar yerləşir. i-ci sətirdə i-1 simvol - sıfırlar və birlər yazılır. Ə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.

Qrafda Hamilton dövrünün mövcud olduğu və hər zirvənin dərəcəsinin N/2-dən az olmadığı təmin edilir.

Çıxış verilənləri

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

Nümunələr