Задача №111118. Осмотр королевства
Давным-давно в одном королевстве правил мудрый король. В том королевстве было \(N\) городов, любые два из которых были соединены дорогой. С целью безопасности дорожного движения, по каждой дороге разрешалось перемещаться только в одну сторону.
Король любил свое королевство. Каждый год он \(K\) раз осуществлял осмотр королевства. Каждый осмотр начинался в столице, затем король, перемещаясь по дорогам, посещал некоторые города и, наконец, прибывал в курортный город на берегу моря, где он отдыхал после нелегкой работы. Таким образом, король посещал каждый город в королевстве ровно один раз в течении года (за исключением столицы, где каждый осмотр начинался, и морского курорта, где каждый осмотр заканчивался).
Но годы уходили, и король становится стар. И ему было все сложнее делать эти \(K\) осмотров. Так что однажды он позвал своего министра транспорта и приказал ему сделать новую программу для осмотра королевства. Осмотр должен начинаться в столице и заканчиваться на морском курорте. Однако теперь весь этот путь должен посещать все города, которые ранее посещались в процессе \(K\) осмотров. И более того, если ранее некоторые города \(A\) и \(B\) посещались в процессе одного осмотра, причем \(A\) посещался до \(B\), то новый осмотр также должен посещать \(A\) до \(B\).
Помогите королю сделать осмотр королевства менее утомительным, разработайте новый маршрут для осмотра.
В первой строке входных данных содержится два целых числа — \(N\) и \(K\) (\(3 \leq N \leq 400, 1 \leq K \leq 100\)). Следующие \(N\) строк описывают дороги. Каждая строка содержит \(N\) символов. \(i\)-й символ \(i\)-й из этих строк равен '.'. Для всех \(i \ne j\) \(j\)-й символ \(i\)-й строки равен '+', если дорога идет из \(j\)-го города в \(i\)-й, либо '-', если дорога идет из \(i\)-го в \(j-й\). Столица имеет номер \(1\), морской курорт имеет номер \(N\).
Следующие \(K\) строк содержат описание маршрутов, по которым король традиционно осуществлял осмотр. Каждый маршрут описывается на одной строке. Каждое описание содержит номера городов в том порядке, в котором король посещал города в процессе соответствующего осмотра. Гарантируется, что каждый осмотр начинается в столице, заканчивается в морском курорте и следует по всем дорогам в корректном направлении. Каждый город, за исключением столицы и морского курорта, посещается ровно в одном маршруте. Ни один маршрут не идет непосредственно из столицы в морской курорт. Ни один маршрут не посещает в качестве промежуточного города столицу или морской курорт.
Выведите N чисел — порядок, в котором следует посещать города. Если выполнить требования короля невозможно, выведите −1.
7 2 .------ +.+---- +-.-+++ +++.--- ++-+.-- ++-++.- ++-+++. 1 3 4 7 1 2 5 6 7
1 3 2 4 5 6 7
\(K \leq 2\). Решение оценивается в \(25\) баллов.
\(K \leq 3\). Решение оценивается в \(25\) баллов.
Дополнительные ограничения отсутствуют. Решение оценивается в \(50\) баллов.