Героиня "Всё, везде и сразу" путешествует по мультивселенной, меняя свои образы в поисках той Эвелин, которая может спасти мир. Но, оказывается, не из любой своей ипостаси Эвелин может сразу перейти в конечную сущность, способную спасти мультивселенную. Переходы между состояниями занимают время, а нужно спешить, люди альфа-вселенной не могут ждать долго.
Помогите Эвелин - найдите самый короткий (по количеству переходных состояний) путь к настоящей Эвелин.
Входные данные
В первой строке находится число: N, (1 <= N <= 1000; - общее количество сущностей Эвелин, В следующих N строках по N чисел - 1 или 0. Стоящий в I-ой строке на J-ом месте 0 означает отсутствие возможности перехода из I-го состояния в J-ое, а стоящая 1 - присутствие. В последней строке находятся два числа S - номер состояния, в котором Эвелин находится в начальный момент времени, и V - номер конечного состояния, в котором нужно оказаться Эвелин.(1 <= S, V <= N)
Выходные данные
Вывести наименьшее число переходов, за которое Эвелин сможет перевоплотиться в нужное состояние, или NO, если из текущего состояния такое сделать невозможно.
| № | Входные данные | Выходные данные |
|
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
|