Задание

Напишите программу, скопируйте код в поле ответа.

В неориентированном графе требуется найти минимальный путь между двумя вершинами.

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

Первым на вход поступает число N – количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной.

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

Выведите сначала L – длину кратчайшего пути (количество ребер, которые нужно пройти), а потом сам путь. Если путь имеет длину 0, то его выводить не нужно, достаточно вывести длину.

Необходимо вывести путь (номера всех вершин в правильном порядке). Если пути нет, нужно вывести -1.

Примеры

входные данные

5

0 1 0 0 1

1 0 1 0 0

0 1 0 0 0

0 0 0 0 0

1 0 0 0 0

3 5

выходные данные

3

3 2 1 5