Pagini recente » Cod sursa (job #2838376) | Cod sursa (job #2613436) | Cod sursa (job #2900860) | Cod sursa (job #2864988) | Cod sursa (job #1638109)
#include <fstream>
#include <queue>
#include <vector>
#include <stack>
#include <list>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
const int DIM = 100004;
int n, m;
list<int> G[DIM], L;
vector<int> grd;
vector<bool> s;
stack<int> S;
void Read();
void Write(int x);
int Result();
int Eulerian();
void BFS(int x);
int main() {
Read();
Write(Result());
fin.close();
fout.close();
return 0;
}
void BFS(int x) {
queue<int> Q;
s[x] = true;
Q.push(x);
while (!Q.empty()) {
x = Q.front(); Q.pop();
for (list<int> :: iterator it = G[x].begin(); it != G[x].end(); ++it)
if (!s[*it]) {
s[*it] = true;
Q.push(*it);
}
}
}
int Eulerian() {
for (int i = 1; i <= n; i++)
if (grd[i] % 2 == 1) return 0;
BFS(1);
for (int i = 1; i <= n; i++)
if (s[i] == false) return 0;
return 1;
}
void Erase(int v, int w) {
grd[v]--, grd[w]--;
G[v].pop_front();
for (list<int> :: iterator it = G[w].begin(); it != G[w].end(); ++it)
if (*it == v){
G[w].erase(it);
break;
}
}
void Euler(int v) {
while (true) {
if (G[v].empty()) break;
int w = G[v].front();
S.push(v);
Erase(v, w);
v = w;
}
}
int Result() {
int v = Eulerian();
if (v == 0) return -1;
do {
Euler(v);
v = S.top(); S.pop();
L.push_back(v);
} while (!S.empty());
return 1;
}
void Write(int x) {
if (x == -1) fout << "-1";
else {
for (list<int> :: iterator it = L.begin(); it != L.end(); ++it)
fout << *it << ' ';
}
}
void Read() {
fin >> n >> m;
grd = vector<int>(n + 1, 0);
s = vector<bool>(n + 1, false);
for (int i = 1, x, y; i <= m; i++) {
fin >> x >> y;
G[x].push_back(y); grd[x]++;
G[y].push_back(x); grd[y]++;
}
}