e-olymp
Məsələlər

Г. турист

Г. турист

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

Г. турист только что прибыл Пингвинными авиалиниями в город 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 (MN2), а вследующей строке (строках) M чисел - номера городов на пути. Первым должен быть город S, последним город F. А для любых двух соседних городов на маршруте должна существовать прямая дорога из одного города в другой.

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri
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
Çıxış verilənləri
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
File Sharing
Heroes of Money and Magic