Pagini recente » Cod sursa (job #955443) | Cod sursa (job #2687471) | Cod sursa (job #659491) | Cod sursa (job #1431701) | Cod sursa (job #1141462)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
const int MAX_N=100100;
vector<int> A[MAX_N];
bool viz[MAX_N];
void dfs(int nod) {
viz[nod]=true;
for(auto it=A[nod].begin(); it!=A[nod].end(); it++) {
if(!viz[*it]) {
dfs(*it);
}
}
}
bool ok(int n) {
dfs(1);
for(int i=1;i<=n;i++) {
if(!viz[i]||A[i].size()%2) {
return false;
}
}
return true;
}
void sterge(int a,int b) {
A[a].pop_back();
for(auto it=A[b].begin(); it!=A[b].end(); it++) {
if(*it==a) {
A[b].erase(it);
return;
}
}
}
vector<int> E;
vector<int> st;
void euler(int nod) {
while(true) {
if(!A[nod].size()) {
break;
}
int f=A[nod].back();
sterge(nod,f);
st.push_back(nod);
nod=f;
}
}
int main() {
int n,m;
fin>>n>>m;
for(int i=1;i<=m;i++) {
int a,b;
fin>>a>>b;
A[a].push_back(b);
A[b].push_back(a);
}
if(!ok(n)) {
fout<<-1;
return 0;
}
int v=1;
E.push_back(1);
do {
euler(v);
v=st.back();
st.pop_back();
E.push_back(v);
} while(st.size());
for(auto it=E.begin(); it<E.end()-1;it++) {
fout<<*it<<' ';
}
return 0;
}