Задача №112645. Путь почтальона

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

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

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

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

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

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