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

Г. турист

Г. турист

Система доріг Лемурії досить складна. Деякі її міста пов'язані між собою односторонніми або двосторонніми дорогами. Тим не менш, лемури тримають дороги в хорошому стані, та їх карти доріг завжди актуальні. Г. турист тільки що прибув Пінгвіними авіалініями у місто \textbf{S} Лемурії. Зворотній рейс відправляється з міста \textbf{F}. У Г. є список найпопулярніших пам'яток Лемурії, усі з яких він збирається відвідати. У нього також є остання версія карти доріг, тобто для кожного міста \textbf{P} у нього є список міст, в які можна потрапити прямо з \textbf{P}. Ваше завдання полягає в тому, щоб допомогти туристу спланувати маршрут через Лемурію. Маршрут повинен починатися в \textbf{S}, проходити через усі міста з пам'ятками (в довільному порядку) і закінчуватися в \textbf{F}. \InputFile Перший рядок містить чотири цілих числа: кількість міст Лемурії \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{2000}), кількість міст з пам'ятками \textbf{K} (\textbf{0} ≤ \textbf{K} ≤ \textbf{N}), та номери міст \textbf{S} та \textbf{F} (усі міста пронумеровані числами починаючи з \textbf{1}). Другий рядок містить \textbf{K} різних чисел - номери міст з пам'ятками. Останні \textbf{N} рядків описують карту доріг. Кожний рядок містить \textbf{N} символів: якщо \textbf{q^\{ий\}} символ \textbf{(p+2)^\{го\}} рядку дорівнює \textbf{1}, то існує пряма дорога з міста \textbf{p} у місто \textbf{q}, якщо він дорівнює \textbf{0}, то прямої дороги не існує. Жодна дорога не веде до міста, в якому починається. \OutputFile Якщо шляху, що задовольняє умовам, немає, то вивести в одному рядку слово "\textbf{NO}". Інакше в першому рядку вивести слово "\textbf{YES}", у другому - кількість міст на шляху \textbf{M} (\textbf{M} ≤ \textbf{N^2}), а у наступному рядку (рядках) \textbf{M} чисел - номери міст на шляху. Першим має бути місто \textbf{S}, останнім місто \textbf{F}. А для будь-яких двох сусідніх міст на маршруті повинна існувати пряма дорога з одного міста в інше.
Ліміт часу 3 секунди
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
4 4 1 2
1 2 3 4
0100
0011
1000
1000
Вихідні дані #1
YES
8
1 2 4 1 2 3 1 2