Г. турист
Г. турист
Система дорог Лемурии достаточно сложна. Некоторые ее города связаны между собой односторонними или двусторонними дорогами. Тем не менее, лемуры содержат дороги в хорошем состоянии и их карты дорог всегда в актуальны.
Г. турист только что прибыл Пингвинными авиалиниями в город S Лемурии. Обратный рейс отправляется из города F. У Г. имеется список самых популярных достопримечательностей Лемурии, все из которых он собирается посетить. У него также есть последняя версия карты дорог, то есть для каждого города P у него имеется список городов, в которые можно попасть напрямую из P. Ваша задача состоит в том, чтобы помочь туристу спланировать маршрут через Лемурию. Маршрут должен начинается в S, проходить через все города с достопримечательностями (в произвольном порядке) и заканчивается в F.
Входные данные
Первая строка содержит четыре целых числа: количество городов Лемурии N (1 ≤ N ≤ 2000), количество городов с достопримечательностями K (0 ≤ K ≤ N), и номера городов S и F (все города пронумерованы числами начиная с 1). Вторая строка содержит K разных чисел - номера городов с достопримечательностями.
Последние N строк описывают карту дорог. Каждая строка содержит N символов: если q^{ый} символ (p+2)^{ой} строки равен 1, то существует прямая дорога из города p в город q, если он равен 0, то прямой дороги не существует. Никакая дорога не ведет в город, в котором начинается.
Выходные данные
Если пути, удовлетворяющего условиям, нет, то вывести в одной строке слово "NO". Иначе в первой строке вывести слово "YES", во второй - количество городов на пути M (M ≤ N^2), а вследующей строке (строках) M чисел - номера городов на пути. Первым должен быть город S, последним город F. А для любых двух соседних городов на маршруте должна существовать прямая дорога из одного города в другой.
Пример
4 4 1 2 1 2 3 4 0100 0011 1000 1000
YES 8 1 2 4 1 2 3 1 2