Wormhouse

题意翻译

## 题目描述 虫子阿尼又吃完了苹果屋，决定搬家。他把所有的房间从1到n编号。所有的走廊都是双向的。 阿尼希望新房子看起来和以前的一样。也就是说，它应该有N个房间，如果在旧房子里有一个从房间I到J室的走廊，它也应该建在新房子里。 我们知道，在建造房屋的过程中，阿尼从某个房间开始吃苹果，直到他穿过所有走廊，回到起点才停下来。众所周知，阿尼吃东西不停。也就是说，直到阿尼把房子盖好，他每时每刻都在忙着啃一条新走廊。阿尼不会沿着已经建成的走廊走。（一笔画） 然而，你换房子的时候，要以同样的顺序啃出走廊是一项非常困难的工作。这就是为什么阿尼知道走廊在前一栋房子里的位置顺序，想用另一个顺序啃走廊。它被表示为一个房间列表，按访问顺序排列。新的顺序应该是字典序上最小的，但是它也应该严格大于之前的字典序。 ## 输入格式 第一行包含两个整数n和m（3<=n<=100，3<=m<=2000）。这是阿尼家相应的房间和走廊的数量。下一行包含m+1个不超过n的正整数。这是对阿尼老路的描述，表现为他在上一个房子期间参观过的房间清单。我们保证清单上的最后一个编号与第一个编号一致。 清单中描述的第一个房间是正门，这就是为什么阿尼应该开始啃它。 你可以假设没有一个房间是和自己相连的，任何一对房间之间最多只有一条走廊。但是，可以找到一些与其他房间断开连接的独立房间。 ## 输出格式 打印不超过n的m+1个正整数。这些数字是对新道路的描述，根据这些编号，阿尼应该按顺序把他的新房子啃光。如果不可能找到新的路径，你应该打印出没有解决方案（"No solution"）。你的答案中的第一个编号应该等于最后一个。它也应该与主入口的编号相等。

题目描述

Arnie the Worm has finished eating an apple house yet again and decided to move. He made up his mind on the plan, the way the rooms are located and how they are joined by corridors. He numbered all the rooms from $ 1 $ to $ n $ . All the corridors are bidirectional. Arnie wants the new house to look just like the previous one. That is, it should have exactly $ n $ rooms and, if a corridor from room $ i $ to room $ j $ existed in the old house, it should be built in the new one. We know that during the house constructing process Arnie starts to eat an apple starting from some room and only stops when he eats his way through all the corridors and returns to the starting room. It is also known that Arnie eats without stopping. That is, until Arnie finishes constructing the house, he is busy every moment of his time gnawing a new corridor. Arnie doesn't move along the already built corridors. However, gnawing out corridors in one and the same order any time you change a house is a very difficult activity. That's why Arnie, knowing the order in which the corridors were located in the previous house, wants to gnaw corridors in another order. It is represented as a list of rooms in the order in which they should be visited. The new list should be lexicographically smallest, but it also should be strictly lexicographically greater than the previous one. Help the worm.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 3<=n<=100,3<=m<=2000 $ ). It is the number of rooms and corridors in Arnie's house correspondingly. The next line contains $ m+1 $ positive integers that do not exceed $ n $ . They are the description of Arnie's old path represented as a list of rooms he visited during the gnawing. It is guaranteed that the last number in the list coincides with the first one. The first room described in the list is the main entrance, that's why Arnie should begin gnawing from it. You may assume that there is no room which is connected to itself and there is at most one corridor between any pair of rooms. However, it is possible to find some isolated rooms which are disconnected from others.

输出格式

Print $ m+1 $ positive integers that do not exceed $ n $ . Those numbers are the description of the new path, according to which Arnie should gnaw out his new house. If it is impossible to find new path you should print out No solution. The first number in your answer should be equal to the last one. Also it should be equal to the main entrance.

输入输出样例

输入样例 #1

3 3
1 2 3 1

输出样例 #1

1 3 2 1 

输入样例 #2

3 3
1 3 2 1

输出样例 #2

No solution