Pagini recente » Cod sursa (job #2748685) | Cod sursa (job #1903084) | Cod sursa (job #355322) | Cod sursa (job #445174) | Cod sursa (job #1964806)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <list>
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
int n,m;
bool U[100005];
bool UE[500005];
vector<pair<int,int>> L[100005];
vector<int> SOL;
void read(){
in>>n>>m;
for(int x,y,i=1;i<=m;i++){
in>>x>>y;
L[x].push_back({y,i});
L[y].push_back({x,i});
}
}
void dfs(int nod){
U[nod]=1;
for(auto x : L[nod])
if(!U[x.first])
dfs(x.first);
}
void euler(int st){
int nod,vecin,id;
stack<int> S;
S.push(st);
while(!S.empty()){
nod=S.top();
if(L[nod].empty()){
S.pop();
SOL.push_back(nod);
}
else{
vecin=L[nod].back().first;
id=L[nod].back().second;
L[nod].pop_back();
if(!UE[id]){
UE[id]=1;
S.push(vecin);
}
}
}
}
void solve(){
dfs(1);
for(int i=1;i<=n;i++){
if(!U[i]||L[i].size()%2!=0){
out<<-1;
return;
}
}
euler(1);
SOL.pop_back();
for(auto x : SOL)
out<<x<<" ";
}
int main(){
read();
solve();
return 0;
}