D. Дом для червя
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Червь по имени Арни уже в который раз догрыз свой дом-яблоко и решил переехать. Он уже давно для себя определил план расположения комнат и коридоров, их соединяющих; пронумеровал все комнаты от 1 до n. Все коридоры двусторонние.

Арни хочет, чтобы новый дом выглядел абсолютно также как и предыдущий, то есть в нём должно быть ровно n комнат и, если в старом доме существовал коридор из комнаты i в комнату j, то этот коридор обязательно должен быть построен и в новом доме.

Известно, что во время постройки своего дома Арни начинает грызть яблоко из некоторой комнаты и остановится лишь тогда, когда прогрызёт все коридоры и вернётся в начальную комнату. Также известно, Арни грызёт, не прерываясь, то есть пока он не закончит строительство, в каждый момент времени он занят прогрызанием нового коридора, по уже построенным коридорам Арни не ходит.

Однако прогрызать коридоры в одном и том же порядке при каждом переезде — занятие скучное. Поэтому он, зная порядок построения коридоров в предыдущем доме, хочет прогрызть коридоры в другом порядке. Этот порядок представляет собой список комнат в процессе их посещения. Новый список должен быть лексикографически наименьший, но строго больше предыдущего. Помогите червю.

Входные данные

В первой строке дано два целых числа n и m (3 ≤ n ≤ 100, 3 ≤ m ≤ 2000) — количество комнат и коридоров в доме Арни соответственно. В следующей строке записано m + 1 натуральных чисел, не превышающих n: описание старого маршрута Арни в виде списка комнат, которые он посещал во время прогрызания. Гарантируется, что последнее число в этом списке совпадает с первым.

Первая комната, описанная во второй строке входного файла — это главный вход, поэтому Арни всегда должен начинать грызть именно с неё.

Вы можете предполагать, что ни одна комната не соединена сама с собой коридором, и если существует коридор между некоторой парой комнат, то только один. В то же время, могут существовать изолированные комнаты, не соединённые коридорами вообще.

Выходные данные

Выведите m + 1 натуральных чисел, не превышающих n: описание нового маршрута Арни, в соответствии с которым он должен прогрызать свой новый дом. Если такого маршрута не существует, выведите No solution. В вашем ответе первое число должно совпадать с m + 1-ым и являться главным входом.

Примеры
Входные данные
3 3
1 2 3 1
Выходные данные
1 3 2 1 
Входные данные
3 3
1 3 2 1
Выходные данные
No solution