#include <fstream>
#include <vector>
using namespace std;
const int MAXN = 100005;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
vector<int> vecini[MAXN];
vector<int> ciclu;
int grad[MAXN];
int n;
void citire()
{
int m;
int a,b;
in >> n >> m;
for (int i = 1;i <= m;++i)
{
in >> a >> b;
vecini[a].push_back(b);
++grad[b];
vecini[b].push_back(a);
++grad[a];
}
}
bool conex()
{
int coada[MAXN] = {0};
int p = 1,q = 1;
bool vizitat[MAXN] = {0};
coada[1] = 1;
vizitat[1] = 1;
while(p <= q)
{
int nod = coada[p];
++p;
for (unsigned int i = 0;i < vecini[nod].size();++i)
{
int vecin = vecini[nod][i];
printf("%d vecin cu %d\n",nod,vecin);
if (!vizitat[vecin])
{
vizitat[vecin] = true;
coada[++q] = vecin;
}
}
}
for (int i = 1;i <= n;++i)
if (!vizitat[i])
return false;
return true;
}
//pentru a fi eulerian trebuie sa fie conex(intre oricare doua noduri sa existe drum)
//si trebuie ca toate nodurile sa aiba grad par
bool eulerian()
{
if (!conex())
return false;
for (int i = 1;i <= n;++i)
if (grad[i] % 2 == 1)
return false;
return true;
}
void sterge(int a, int b)
{
int i;
for (i = 0;vecini[a][i] != b;++i);
vecini[a].erase(vecini[a].begin() + i);
for (i = 0;vecini[b][i] != a;++i);
vecini[b].erase(vecini[b].begin() + i);
}
/*
implementare iterativa a pseudocodului:
euler (nod v)
cat timp (v are vecini)
w = un vecin aleator al lui v
sterge_muchie (v, w)
euler (w)
sfarsit cat timp
adauga v la ciclu
*/
void generare_ciclu()
{
int stiva[MAXN] = {0};
int q = 1;
stiva[1] = 1;
while(q > 0)
{
int nod = stiva[q];
if (vecini[nod].size() > 0)
{
int vecin = vecini[nod][vecini[nod].size() - 1];
sterge(nod,vecin);
stiva[++q] = vecin;
}
else
{
ciclu.push_back(nod);
--q;
}
}
}
int main()
{
citire();
if (!eulerian())
out << "-1";
else
{
generare_ciclu();
for (unsigned int i = 0;i < ciclu.size() - 1;++i)
out << ciclu[i] << ' ';
out << '\n';//fara ultimul element, asa e cerinta
}
return 0;
}