Pagini recente » Cod sursa (job #3157898) | Cod sursa (job #2068011) | Cod sursa (job #1352516) | Cod sursa (job #671137) | Cod sursa (job #804154)
Cod sursa(job #804154)
#include<cstdio>
#include<cassert>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int n, m;
vector<pair<int, int> > graph[100005];
pair<int, int> edg[500005];
int num[100005], ind[100005], viz[500005];
void read(){
assert(freopen("ciclueuler.in", "r", stdin));
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++i){
int x, y;
scanf("%d%d", &x, &y);
++num[x];
++num[y];
edg[i] = make_pair(x, y);
graph[x].push_back(make_pair(i, y));
graph[y].push_back(make_pair(i, x));
}
}
vector<int> ans;
vector<pair<int, int> > systack;
int aux, x, e;
void dfs(){
e = systack.back().first;
x = systack.back().second;
while(ind[x] < graph[x].size()){
if(!viz[graph[x][ind[x]].first]){
viz[graph[x][ind[x]].first] = 1;
aux = ind[x];
++ind[x];
systack.push_back(make_pair(graph[x][aux].first, graph[x][aux].second));
dfs();
e = systack.back().first;
x = systack.back().second;
}
else
++ind[x];
}
if(x == edg[e].first)
ans.push_back(edg[e].second);
else
ans.push_back(edg[e].first);
systack.pop_back();
}
void write(){
assert(freopen("ciclueuler.out", "w", stdout));
if(ans.size() - 1 != m){
printf("-1\n");
return;
}
for(int i = 0; i < ans.size() - 1; ++i)
printf("%d ", ans[i]);
}
int main(){
read();
int isk = 1;
for(int i = 1; i <= n; ++i)
if(num[i] % 2 != 0)
isk = 0;
if(isk){
systack.push_back(make_pair(0,1));
dfs();
}
write();
return 0;
}