eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Г. турист

Г. турист

Лимит времени 3 секунды
Лимит использования памяти 256 MiB

Система дорог Лемурии достаточно сложна. Некоторые ее города связаны между собой односторонними или двусторонними дорогами. Тем не менее, лемуры содержат дороги в хорошем состоянии и их карты дорог всегда в актуальны.

Г. турист только что прибыл Пингвинными авиалиниями в город S Лемурии. Обратный рейс отправляется из города F. У Г. имеется список самых популярных достопримечательностей Лемурии, все из которых он собирается посетить. У него также есть последняя версия карты дорог, то есть для каждого города P у него имеется список городов, в которые можно попасть напрямую из P. Ваша задача состоит в том, чтобы помочь туристу спланировать маршрут через Лемурию. Маршрут должен начинается в S, проходить через все города с достопримечательностями (в произвольном порядке) и заканчивается в F.

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

Первая строка содержит четыре целых числа: количество городов Лемурии N (1N2000), количество городов с достопримечательностями K (0KN), и номера городов S и F (все города пронумерованы числами начиная с 1). Вторая строка содержит K разных чисел - номера городов с достопримечательностями.

Последние N строк описывают карту дорог. Каждая строка содержит N символов: если q^{ый} символ (p+2)^{ой} строки равен 1, то существует прямая дорога из города p в город q, если он равен 0, то прямой дороги не существует. Никакая дорога не ведет в город, в котором начинается.

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

Если пути, удовлетворяющего условиям, нет, то вывести в одной строке слово "NO". Иначе в первой строке вывести слово "YES", во второй - количество городов на пути M (MN^2), а вследующей строке (строках) M чисел - номера городов на пути. Первым должен быть город S, последним город F. А для любых двух соседних городов на маршруте должна существовать прямая дорога из одного города в другой.

Пример

Входные данные #1
4 4 1 2
1 2 3 4
0100
0011
1000
1000
Выходные данные #1
YES
8
1 2 4 1 2 3 1 2