Pagini recente » Cod sursa (job #143473) | Cod sursa (job #2477137) | Cod sursa (job #2380335) | Cod sursa (job #2517647) | Cod sursa (job #1235785)
#include <cstdio>
#define max_n 100020
#include <queue>
#include <vector>
#include <list>
using namespace std;
struct stk{
int node;
stk *link;
} *st;
int n,m;
list <int> q[max_n];
vector <int> ls;
queue <int> kj;
int grd[max_n];
int s[max_n];
inline void add_stn(stk *&f,int x){
if(f==NULL){
f=new stk;
f->node=x;
f->link=NULL;
return;
}
stk *c=new stk;
c->node=x;
c->link=f;
f=c;
}
inline void del_stn(stk *&f){
stk *c=f;
f=f->link;
delete c;
}
void read(){
freopen("ciclueuler.in","r",stdin);
scanf("%d %d",&n,&m);
int x,y;
while(m--){
scanf("%d%d",&x,&y);
grd[x]++;
q[x].push_back(y);
grd[y]++;
q[y].push_back(x);
}
}
void solve(){
int i,r,t;
kj.push(1);
while(!kj.empty()){
i=kj.front();
kj.pop();
s[i]=1;
for(list <int> :: iterator it=q[i].begin();it!=q[i].end();++it)
if(!s[*it])
kj.push(*it);
}
for(i=1;i<=n;i++)
if((grd[i]%2)||(!s[i])){
printf("-1\n");
return;
}
r=1;
do{
while(!q[r].empty()){
t=q[r].front();
add_stn(st,r);
q[r].pop_front();
grd[r]--;
grd[t]--;
for(list <int> ::iterator it=q[t].begin();it!=q[t].end();++it)
if(*it == r){
q[t].erase(it);
break;
}
r=t;
}
r=st->node;
del_stn(st);
ls.push_back(r);
}while(st!=NULL);
for(vector <int> :: iterator tr=ls.begin();tr!=ls.end();++tr)
printf("%d ",*tr);
printf("\n");
}
int main()
{
read();
freopen("ciclueuler.out","w",stdout);
solve();
return 0;
}