Pagini recente » Cod sursa (job #2953119) | Cod sursa (job #2957098) | Cod sursa (job #2771889) | Cod sursa (job #2340849) | Cod sursa (job #2477574)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
const int nmax = 100000;
vector <int> g[nmax + 5], sol;
stack <int> st;
int n, m, grad[nmax + 5];
bool use[nmax + 5];
void Read(){
fin >> n >> m;
while (m--){
int x, y;
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
grad[x]++; grad[y]++;
}
}
void DFS(int nod){
use[nod] = 1;
for (auto i : g[nod])
if (!use[i])
DFS(i);
}
int Check(){
DFS(1);
for (int i = 1; i <= n; i++)
if (grad[i] % 2 || (!use[i] && grad[i]))
return 0;
return 1;
}
void Delete(int nod, int vecin){
g[nod].erase(g[nod].begin());
for (int i = 0; i < g[vecin].size(); i++)
if (g[vecin][i] == nod){
g[vecin].erase(g[vecin].begin() + i);
return;
}
}
void Cycle(int nod){
while (g[nod].size()){
int vecin = g[nod][0];
st.push(nod);
Delete(nod, vecin);
nod = vecin;
}
}
void Solve(){
int nod = 1;
do{
Cycle(nod);
nod = st.top();
st.pop();
sol.push_back(nod);
}while(!st.empty());
}
void Print(){
for (auto i : sol)
fout << i << ' ';
fout << '\n';
}
int main(){
Read();
if (!Check()){
fout << "-1\n";
return 0;
}
Solve();
Print();
return 0;
}