Pagini recente » Cod sursa (job #3238057) | Cod sursa (job #2804388) | Cod sursa (job #1965298) | Cod sursa (job #3131334) | Cod sursa (job #815491)
Cod sursa(job #815491)
#include <cstdio>
#include <cstring>
#include <list>
#include <stack>
#include <vector>
using namespace std;
inline int next_int() {
int n = 0;
char c = getchar_unlocked();
while (!('0' <= c && c <= '9')) {
c = getchar_unlocked();
}
while ('0' <= c && c <= '9') {
n = n * 10 + c - '0';
c = getchar_unlocked();
}
return n;
}
const int V = 100000 + 1;
const int E = 500000 + 500000;
int deg[V], root[V], seen[E];
list<int> G[V];
vector<int> tour;
stack<int> stk;
int find(int u) {
return (root[u] == u) ? (u) : (root[u] = find(root[u]));
}
inline void merge(int u, int v) {
root[find(u)] = find(v);
}
inline void euler(int u) {
while (!G[u].empty()) {
stk.push(u);
int v = G[u].front();G[u].pop_front();
for (list<int>::iterator it = G[v].begin(); it != G[v].end(); it++) {
if (*it == u) {
G[v].erase(it);
break;
}
}
u = v;
}
}
inline void find_euler_tour(int v) {
do {
euler(v);
v = stk.top();
stk.pop();
tour.push_back(v);
} while (!stk.empty());
}
int main() {
freopen("ciclueuler.in", "r", stdin);
freopen("ciclueuler.out", "w", stdout);
const int n = next_int();
const int m = next_int();
for (int i = 1; i <= n; i++) {
root[i] = i;
}
for (int i = 0; i < m; i++) {
int u = next_int(), v = next_int();
deg[u]++, deg[v]++;
G[u].push_back(v), G[v].push_back(u);
merge(u, v);
}
int ok = true;
for (int i = 1; i <= n; i++) {
if ((deg[i] & 1) || find(i) != find(1)) {
ok = false;
}
}
if (ok) {
find_euler_tour(1);
for (int i = tour.size() - 1; i >= 0; i--) {
printf("%d ", tour[i]);
}
} else {
printf("-1");
}
return 0;
}