Pagini recente » Cod sursa (job #2848434) | Cod sursa (job #703550) | Cod sursa (job #2555968) | Cod sursa (job #2721440) | Cod sursa (job #3268300)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5+2;
const int MMAX = 5e5+2;
using pii = pair<int, int>;
int n,m;
bool used[MMAX],vis[NMAX];
vector<pii> v[NMAX];
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
vector<int> findEulerCycle(){
stack<int> st;
vector<int> g(n+1);
for(int i = 1; i <= n; i++){
g[i] = v[i].size();
}
st.push(1);
vector<int> ans;
while(!st.empty()){
int nod = st.top();
vis[nod] = true;
if(g[nod] == 0){
ans.push_back(nod);
st.pop();
}else{
int len = v[nod].size();
auto [vecin, idx] = v[nod][len-g[nod]];
if(used[idx] == false){
st.push(vecin);
used[idx] = true;
}
g[nod]--;
}
}
return ans;
}
int main() {
fin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y;
fin >> x >> y;
v[x].push_back({y, i});
v[y].push_back({x, i});
}
bool ok = true;
for(int i = 1; i <= n; i++){
ok &= (v[i].size()%2 == 0);
}
vector<int> cycle = findEulerCycle();
for(int i = 1; i <= n; i++){
ok &= vis[i];
}
if(ok){
cycle.pop_back();
for(int nod: cycle){
fout << nod << " ";
}
}else{
fout << "-1";
}
return 0;
}