Задача "Бело-черный граф"

Дан неориентированный граф без петель и кратных ребер. В этом графе некоторые ребра покрашены в черный цвет, а остальные - в белый. Длиной из вершины A в вершину B называется количество ребер, которые нужно пройти, чтобы из вершины A попасть в B.

В этом графе при следовании из вершины A в вершину B разрешается пройти не более чем по одному черному ребру (по белым ребрам можно проходить сколько угодно раз). Найдите длину такого кратчайшего пути из A в B.

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

Сначала вводится число N - количество вершин в графе (2≤N≤50). Далее записана матрица смежности. 0 обозначает отсутствие ребра, 1 - ребро белого цвета, 2 - ребро черного цвета. Далее записаны числа A и B - номера начальной и конечной вершины.

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

Выведите одно число - минимальную длину пути из A в B, проходящего не более, чем по одному черному ребру. Если такого пути не существует, выведите -1.

Примеры

Пример вводаПример выводаКомментарий
5
0 1 0 2 0
1 0 0 0 1
0 0 0 1 1
2 0 1 0 0
0 1 1 0 0
1 3
2
Существует путь только по белым ребрам, проходящий через вершины 1, 2, 5, 3, а существует путь длиной 2, проходящий по одному черному (1 4) и одному белому (4 3) ребру.
5
0 1 0 2 0
1 0 0 0 1
0 0 0 2 1
2 0 2 0 0
0 1 1 0 0
1 3
3
Существует путь длины 2: 1, 4, 3, но он проходит по двум черным ребрам, поэтому ответом является путь 1, 2, 5, 3.
5
0 2 0 2 0
2 0 0 0 2
0 0 0 2 2
2 0 2 0 0
0 2 2 0 0
1 3
-1
Нельзя дойти от 1 до 3, пройдя по черному ребру только один раз.