蠕虫阿尼再次吃完苹果屋并决定搬家。他对平面图、房间的位置以及走廊的连接方式做出了决定。他把所有房间从1到n编号。所有走廊都是双向的。
阿尼希望新房子看起来和以前的一样。也就是说,它应该有n个房间,如果老房子里有从i房间到j房间的走廊,那么它应该建在新房子里。
我们知道,在建造房屋的过程中,阿尼从某个房间开始吃苹果,只有当他吃完所有走廊并返回起始房间时才停止。众所周知,阿尼吃得不停。也就是说,在阿尼完成房子建造之前,他每时每刻都在忙于啃一条新走廊。阿尼没有沿着已经建成的走廊移动。
然而,每当你换房子时,以相同的顺序啃掉走廊是一项非常困难的活动。这就是为什么阿尼知道前一所房子的走廊的顺序,想要以另一种顺序啃走廊。它表示为按访问顺序排列的房间列表。新列表应按字典顺序最小,但严格按字典顺序也应大于前一个列表。帮助蠕虫。
输入
第一行包含两个整数 n 和 m (3 ≤ n ≤ 100, 3 ≤ m ≤ 2000)。对应的是阿尼家的房间数和走廊数。下一行包含 m + 1 个不超过 n 的正整数。它们是对阿尼旧路的描述,以他在啃咬期间访问过的房间列表的形式表示。确保列表中的最后一个数字与第一个数字一致。
列表中描述的第一个房间是主入口,这就是为什么阿尼应该从它开始啃咬。
您可以假设没有任何房间与其自身相连,并且任意一对房间之间最多有一个走廊。然而,也可能会发现一些与其他房间不相连的孤立房间。
输出
打印 m + 1 个不超过 n 的正整数。这些数字是对新道路的描述,根据这条道路,阿尼应该啃掉他的新房子。如果无法找到新路径,您应该打印出“无解决方案”。答案中的第一个数字应等于最后一个数字。它还应该等于主入口。
示例
输入 #1
3 3 1 2 3 1
输出 #1
1 3 2 1
输入 #2
3 3 1 3 2 1
输出 #2
No solution