Задача №112643. Туры с ограниченной стоимостью

Вася решил немного попутешествовать и выяснил, что между некоторыми городами нет прямых авиарейсов, поэтому придётся лететь с пересадками. Ему стало интересно, сколько есть маршрутов между городами A и B , у которых общая стоимость перелёта меньше W рублей. Напишите программу, которая поможет Васе.

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

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

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

В первой строке программа должна вывести количество найденных подходящих маршрутов M . В следующих M строках выводятся сами маршруты в виде последовательности номеров городов, которые нужно посетить. Маршруты должны быть упорядочены. Сначала выводятся самые короткие маршруты (с наименьшим числом пересадок). Среди маршрутов одинаковой длины – сначала маршруты, у которых второй номер города имеет минимально возможный номер, из них сначала все маршруты, в которых третий номер города имеет минимально возможный номер, и т.д.

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