Время

01:34:09
20 May 2012
Версия для печати

Г. турист

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

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


Технические условия

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

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

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

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

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


Информация о задаче

Лимит времени: 3 секунды
Лимит памяти: 256 MB
Баллы за пройденный тест: 1.28205
Классификация: Теория графов

Пример

Пример входных данных

Sample 1
4 4 1 2
1 2 3 4
0100
0011
1000
1000

Sample 2
4 2 1 4
2 3
0110
0001
0001
0000

Sample 3
4 1 2 3
4
0010
1001
1000
0100

Пример выходных данных

Sample 1
YES
8
1 2 4 1 2 3 1 2

Sample 2
NO

Sample 3
YES
7
2 4 2 1 3 1 3


Список задач