← 返回题目列表

Codeforces · 62/D

D. 虫屋

中文机器翻译题面 查看原题

蠕虫阿尼再次吃完苹果屋并决定搬家。他对平面图、房间的位置以及走廊的连接方式做出了决定。他把所有房间从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