Б9123 - Основы алгоритмизации и программирования (2 семестр)

Задача D7. Домино ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	А. Кленин	Ограничение времени:	3 сек
Входной файл:	input.txt	Ограничение памяти:	2 Мб
Выходной файл:	output.txt

Условие

Костяшка домино описывается парой цифр от 0 до 6, например 06 или 33. Цепочка - это последовательность костяшек, скложенных таким образом, чтобы соседние цифры на них совпадали. При этом костяшки можно переворачивать. Например, 15-54-44-46-60 — цепочка.

Дана строка из 2N символов (цифр), задающая N костяшек домино. Требуется переставить все эти костяшки таким образом, чтобы они образовали цепочку, либо определить, что это невозможно. Если существует несколько способов, вывести любой из них.

Формат входного файла

Входной файл содержит строку, задающую костяшки.

Формат выходного файла

В выходном файле должна содержаться единственная строка вида d₁-d₂-...-d_N, где d₁, d₂, …, d_N — костяшки из исходного набора, или NO, если сложить цепочку невозможно.

Ограничения

2 ≤ N ≤ 21

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`1234`	`NO`
2	`453335`	`45-53-33`