Cod sursa(job #871942)
#include <fstream>
#include <cstdio>
#include <vector>
#include <stack>
#include <list>
#include <queue>
using namespace std;
int n,m;
list < int > Graf[100001];
vector < int > eulerian;
stack < int > ST;
queue < int > q;
int grad[100001],vizitat[100001];
void citesc(){
int xs,ys;
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&xs,&ys);
Graf[xs].push_back(ys);
grad[xs]++;
Graf[ys].push_back(xs);
grad[ys]++;
}
fclose(stdin);
}
void BFS(int nod){
vizitat[nod] = 1;
q.push(nod);
int first;
while(!q.empty()){
first = q.front();
q.pop();
for(list < int > ::iterator it = Graf[first].begin();it!=Graf[first].end();++it)
if(!vizitat[*it]){
vizitat[*it] = 1;
q.push(*it);
}
}
}
int conex(){
BFS(1);
for(int k=2;k<=n;k++)
if(vizitat[k] == 0)
return 0;
return 1;
}
int is_eulerian(){
if(!conex())
return 0;
for(int i=1;i<=n;i++)
if(grad[i]%2==1)
return 0;
return 1;
}
void sterg(int v, int w){
grad[v]--; grad[w]--;
Graf[v].pop_front();
for(list < int > ::iterator it = Graf[w].begin();it!=Graf[w].end();++it){
if(*it == v){
Graf[w].erase(it);
break;
}}
}
void euler(int v){
while(true){
if(Graf[v].empty())
break;
int w = Graf[v].front();
ST.push(v);
sterg(v,w);
v=w;
}
}
int solve(){
int v = is_eulerian();
if(!v)
return -1;
do{
euler(v);
v = ST.top();
ST.pop();
eulerian.push_back(v);
}while(!ST.empty());
return 1;
}
void afisez(int ok){
if(ok == -1)
printf("-1\n");
else
for(vector < int > ::iterator it = eulerian.begin();it!=eulerian.end();++it)
printf("%d ", *it);
}
int main(){
citesc();
afisez(solve());
fclose(stdout);
return 0;
}