Cod sursa(job #713042)
#include <fstream>
#include <vector>
#include <stack>
#include <list>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
#define dim 100005
list <int> v[dim*5];
stack <int> stiva;
stack <int> sol;
int viz[dim], n, m, grad[dim];
void read()
{
int i, a, b;
fin>>n >>m;
for(i=1;i<=m;++i)
{
fin>>a >>b;
v[a].push_back(b);
v[b].push_back(a);
++grad[a];
++grad[b];
}
}
int check()
{
for(int i=1;i<=n;++i)
if(grad[i]%2==1)
return 0;
return 1;
}
void euler()
{
list <int> ::iterator it;
int i, next;
for(stiva.push(1);!stiva.empty();)
{
int re=stiva.top();
if(v[re].empty()!=0)
{
sol.push(re);
stiva.pop();
}
else
{
stiva.push(*v[re].begin());
v[re].pop_front();
next=stiva.top();
for(it=v[next].begin();it!=v[next].end();++it)
if(*it==re)
{
v[next].erase(it);
break;
}
}
}
for(;sol.size()>1;sol.pop())
fout<<sol.top() <<" ";
}
int main()
{
read();
if(check()==0)
fout<<"-1";
else
euler();
return 0;
}