Migrated from Lutece 739 昀昀的网络连接

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

昀昀是个天(DaBen)才(Dan),有天她很无聊，于是决定把基地的网线乱接起来。首先她把基地的电脑排成两排，每排有$n$台电脑，昀昀把第一排的每个电脑与第二排的一台电脑相连，同样的，每个第二排的电脑只与第一排唯一一台电脑相连，连完以后昀昀发现所有的网线刚好拉直，于是很开心，可是问题来了，昀昀忘记了第一排的每台电脑到底与第二排的哪一台电脑相连，于是她不开心了。为了弄清楚这个问题她开始整理网线了，第一排第1台连出来的网线和第一排第3台连出的网线交叉，第一排第2台连出来的网线和第一排第3台连出的网线交叉，第一排第4台连出来的网线和第一排第5台连出的网线交叉……可是交叉点好多啊，昀昀算不过来了，于是她伤心地蹲在墙角里哭了，现在，你要去安慰昀昀，唯一的办法就是帮她解决这个问题

Input

包含多组数据。对于每组数据，第一行包含两个整数$n$（$1\le n\le 100000$）和$m$($0\le m\le 100000$)分别表示每排电脑的台数和已知网线交叉的位置数（信息可能不完全）。接下来的$m$行每行包含两个整数$u$和$v$（$1\le u,v\le n$且$u\ne v$），表示第一排第$u$台连出来的网线和第一排第$v$台连出的网线交叉

Output

如果不存在一种方案满足给定的交叉关系，输出$-1$，否则依次输出第二排第一台电脑，第二台电脑，……，第$n$台电脑分别与第一排的哪台电脑相连接，如果有多解，输出字典序最小的一组解

Samples

3 2
1 3
2 3

3 1 2

Note

在输入样例中，以下两种情况都是可行解

但是情况1得到的答案是3 1 2，情况二得到的答案是3 2 1，第一种情况字典序较小，故答案为3 1 2

Resources

2013 UESTC ACM Training for Graph Theory