Pagini recente » Cod sursa (job #1501985) | Cod sursa (job #2649339) | Cod sursa (job #1254157) | Cod sursa (job #252979) | Cod sursa (job #1366268)
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fs first
#define sc second
#define pob pop_back
#define pub push_back
#define eps 1E-7
#define sz(a) a.size()
#define count_one __builtin_popcount;
#define count_onell __builtin_popcountll;
#define fastIO ios_base::sync_with_stdio(false)
#define PI (acos(-1.0))
#define linf (1LL<<62)//>4e18
#define inf (0x7f7f7f7f)//>2e9
#define DEBUG 1
#ifdef DEBUG
#define D(x) x
#else
#define D(x)
#endif
#define MAXN 100010
FILE *in = fopen("ciclueuler.in", "r");
FILE *out = fopen("ciclueuler.out", "w");
int n, m;
int deg[MAXN];
vector<int> vec[MAXN], ciclu;
bitset<MAXN> viz;
stack<int> Q;
void dfs(int nod) {
viz[nod] = 1;
for(auto it = vec[nod].begin(); it != vec[nod].end(); ++it)
if(!viz[*it])
dfs(*it);
}
bool isConex() {
dfs(1);
for(int i = 1; i <= n; ++i)
if(!viz[i])
return false;
return true;
}
bool isEuler() {
if(!isConex())
return false;
for(int i = 1; i <= n; ++i)
if(deg[i] % 2)
return false;
return true;
}
void euler() {
int nod, x;
Q.push(1);
while(!Q.empty()) {
nod = Q.top(); Q.pop();
while(!vec[nod].empty()) {
x = *vec[nod].begin();
vec[nod].erase(vec[nod].begin());
for(auto it = vec[x].begin(); it != vec[x].end(); it++)
if(*it == nod) {
vec[x].erase(it);
break;
}
Q.push(nod);
nod = x;
}
ciclu.pub(nod);
}
}
void solve() {
if(isEuler()) {
euler();
for(auto it = ciclu.begin(); it != ciclu.end(); it++) {
fprintf(out, "%d ", *it);
}
} else {
fprintf(out, "-1\n");
}
}
int main()
{
int x, y;
fscanf(in, "%d%d", &n, &m);
for(int i = 0; i < m; ++i) {
fscanf(in, "%d%d", &x, &y);
vec[x].pub(y); deg[x]++;
vec[y].pub(x); deg[y]++;
}
solve();
return 0;
}