Задача 22. Длиннейший путь ≡

Условие

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

Помогите Догнатий-Перегнатию дойти до дома как можно дольше.

Формат входных данных

На вход подается число N, S и E .

N - количество перекрестков.

S - начальный перекресток.

E - конечный перекресток.

После чисел следует матрица смежности графа размерностью N с расстоянием от одного перекрестка до следующего.

Формат выходных данных

Вывести длину максимального пути.

Ограничения

3 ≤ N ≤ 16

0 ≤ S ≤ 15

0 ≤ E ≤ 15

Примеры тестов

6 1 3
0 13 2 49 0 35
13 0 0 30 46 50
2 0 0 14 0 35
49 30 14 0 12 45
0 46 0 12 0 46
35 50 35 45 46 0
            

206

4 2 3
0 19 25 21
19 0 43 15
25 43 0 15
21 15 15 0
            

61