Стихосложение
Задачу добавил: alef
Успешно сдано решений: 5
Время на тест - до 4 с
Когда Хасан миновал коридор, и открыл дверь, он увидел древнего старца, склонившегося над большим листом бумаги
- Проходи, все уже приготовлено... - старец смотрел на него почти выцветшими глазами. - Тебе осталось только открыть еще одну дверь. Вот эту...
- Разве это дверь? - Хасан провел ладонью по стене
- Дверь. Видишь углубления в камнях? В каждое углубление надо положить по одной табличке. Вот они, эти таблички, на столе. На каждой из них выгравировано слово на древнем языке. Эти слова образуют прекрасные стихи. Но вряд ли ты знаешь этот древний язык...
Хасан взял в руки несколько табличек. Увы, язык ему знаком не был.
- Если пытаться перебрать все возможные варианты, то тебе может всей жизни не хватить, чтобы сложить их в нужной последовательности. Но есть одно приспособление, которое может тебе помочь, - старец показал на матовый диск, лежащий на столе. - Положим на него какую-нибудь табличку. А теперь попробуем положить вторую...
- И что будет? - спросил Хасан.
- Подожди немного, увидишь...
Спустя пару минут старец вздохнул:
- Жаль, ничего не произошло. Бывает и так. Попробуем положить другую...
Когда старец заменил табличку, диск стал прозрачным:
- Ну вот, это значит, что первая табличка находилась левее второй.
- А это приспособление может ошибаться? - спросил Хасан
- Нет, оно может просто ничего не сообщить. Если диск становится прозрачным, то первая табличка точно находилась левее второй. А вот если он не меняется, то не стоит думать, что дело обстояло наоборот. Вот на этом листе записаны результаты успешных измерений для разных пар табличек, первым идет слово, которое находится левее. Попробуй расположить таблички в нужном порядке.
Формат входного файла input.txt
Первая строка - два целых числа N (2 <= N <= 50) и M (1 <= M <= 5000); N - количество табличек, M - количество измерений
Каждая из следующих M строк содержит по два непустых слова через пробел (не длиннее 250 символов каждое).
Известно, что слова на табличках не повторяются, и каждое слово хотя бы один раз встречается в результатах измерений.
Формат выходного файла output.txt
Первая строка - слово SUCCESS, если данных достаточно для построения правильной последовательности
Вторая строка - правильная последовательность слов через пробел
либо
Первая строка - слово AMBIGOUS, если данных недостаточно для построения правильной последовательности
Вторая строка - один из возможных вариантов последовательности слов (через пробел)
Третья строка - другой возможный вариант последовательности слов (через пробел, вариант должен отличаться от приведенного во второй строке)
Пример входного файла
9 13
will to
believe my
verse come
Who in
my to
verse time
will come
Who verse
will time
my time
time come
verse to
Who will
Пример выходного файла
AMBIGOUS
Who will believe my verse in time to come
Who believe will verse my to in time come