Задачі
Пошук гамільтонового циклу в умовах т-ми Хватала
Пошук гамільтонового циклу в умовах т-ми Хватала
Задано граф з \textbf{N} вершин, для якого виконується умовае теореми Хватала, тобто, у відсортованій послідовності його степенів вершин \textbf{d_k} для довільного \textbf{k} < \textbf{n/2} вірно або \textbf{d_k} > \textbf{k}, або \textbf{d_\{n - k\}} ≥ \textbf{n-k}. Ваша задача - знайти гамільтонів цикл.
\InputFile
У першому рядку вхідного файлу записано ціле число \textbf{N} (\textbf{3} ≤ \textbf{N} ≤ \textbf{100}) - кількість вершин у графі. У наступних \textbf{N} рядках записана матриця суміжності. Та як матриця суміжності симетрична, а на діагоналі завжди стоять нулі, у \textbf{i}-му рядку записано \textbf{i-1} символ - нулі та одиниці. Якщо \textbf{j}-й символ \textbf{i}-го рядка дорівнює одиниці, значить є ребро між вершинами \textbf{i} та \textbf{j}.
\OutputFile
Виведіть перестановку з \textbf{N} чисел - номери вершин у порядку гамільтонового циклу.
Вхідні дані #1
4 1 11 101
Вихідні дані #1
1 2 3 4