eolymp
bolt
Try our new interface for solving problems
Məsələlər

Г. турист

Г. турист

Система дорог Лемурии достаточно сложна. Некоторые ее города связаны между собой односторонними или двусторонними дорогами. Тем не менее, лемуры содержат дороги в хорошем состоянии и их карты дорог всегда в актуальны. Г. турист только что прибыл Пингвинными авиалиниями в город \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}. А для любых двух соседних городов на маршруте должна существовать прямая дорога из одного города в другой.
Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
4 4 1 2
1 2 3 4
0100
0011
1000
1000
Çıxış verilənləri #1
YES
8
1 2 4 1 2 3 1 2