墨西哥城建立在一个美丽的盆地中，被称为墨西哥谷，多年前这里大部分是湖泊。大约在公元 1300 年，阿兹特克宗教领袖下令填平湖中心，以建造他们帝国的首都。今天，湖泊已被完全覆盖。

在阿兹特克人到达之前，有 $c$ 座城市位于湖泊周围的岸边。其中一些城市建立了商业协议。拥有商业协议的城市之间通过船只进行货物贸易。任何两座城市都可以通过穿过湖泊的线段相连。

最终，这些城市的国王决定组织这种商业活动。他们设计了一条连接湖泊周围每一座城市的商业路线。该路线满足以下要求：

• 它可以从任何一座城市出发，访问湖泊周围的每一座城市，并最终在与出发城市不同的另一座城市结束。
• 路线访问每一座城市恰好一次。
• 路线中每一对连续访问的城市之间都有商业协议。
• 路线中每一对连续访问的城市之间都由一条线段连接。
• 为了避免船只碰撞，路线从不自交。

该图显示了湖泊及其周围的城市。线条（粗线和细线）代表城市之间的商业协议。粗线代表一条从城市 2 出发并以城市 5 结束的商业路线。这条路线从不自交。例如，构造一条从 2 到 6 到 5 再到 1 的路线是不合法的，因为该路线会自交。

湖泊中的城市按顺时针方向编号为 1 到 $c$。

任务

编写一个程序，给定城市数量 $c$ 以及它们之间的商业协议列表，构造一条满足上述要求的商业路线。

数据范围

$3 \le c \le 1000$：湖泊周围的城市数量。

输入格式

第一行包含整数 $c$。 第二行包含一个整数 $n$，表示商业协议的数量。 接下来的 $n$ 行：每行代表一个唯一的商业协议。每行包含两个用空格分隔的整数，表示协议涉及的两座城市。

输出格式

如果可以构造出商业路线，则输出 $c$ 行，每行包含一个整数，表示商业路线中访问城市的顺序。如果无法构造出满足所有要求的商业路线，则输出一行，包含数字 -1。

说明

如果存在多条满足要求的商业路线，输出其中任何一条均被视为正确。

样例

输入格式 1

7
9
1 4
5 1
1 7
5 6
2 3
3 4
2 6
4 6
6 7

输出格式 1

2
3
4
1
7
6
5

评分

对于总分 40 分的一组测试用例，每个测试用例满足以下要求： $3 \le c \le 20$