Задача №112646. Путь почтальона - 2

Почтальон Печкин ежедневно разносит письма и газеты жителям Простоквашино. Деревня большая, люди живут на хуторах. Печкин хочет каждый день обязательно обойти все хутора и пройти по каждой дороге в Простоквашино. При этом Печкин не хочет дважды проходить по одной дороге. Лучше, конечно, если найдётся маршрут, который и начинается, и заканчивается на почте (это хутор с номером 1). Если так не получается, нужно вывести подходящий маршрут, который начинается с хутора с наименьшим возможным номером. Напишите программу, которая поможет Печкину выбрать подходящий маршрут.

Входные данные

В первой строке вводится количество хуторов N ( 1 ≤ N ≤ 20 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы матрицы смежности графа, который описывает схему расположения хуторов.

Выходные данные

Если нужного маршрута не существует, программа должна вывести число 0. Если маршрут существует, нужно вывести номера все хуторов, через которые последовательно проходит маршрут, начиная с наименьшего возможного номера хутора. Если есть несколько вариантов маршрута, нужно вывести тот, в котором второй номер – минимально возможный. Аналогично третий номер должен быть минимально возможным при выбранных первых двух и т.д.

Примеры
Входные данные
5
0 1 1 0 0
1 0 1 0 0
1 1 0 1 0
0 0 1 0 1
0 0 0 1 0
Выходные данные
3 1 2 3 4 5 
Сдать: для сдачи задач необходимо войти в систему