Pagini recente » Cod sursa (job #675170) | Cod sursa (job #337717) | Cod sursa (job #720308) | Cod sursa (job #1125478) | Cod sursa (job #1147607)
/*
Keep It Simple!
*/
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include<stdio.h>
#include<list>
#include<stack>
#define MaxN 100001
using namespace std;
int N, M;
list<int> G[MaxN],Eu;
stack<int> Queue;
bool viz[MaxN];
void DFS(int node)
{
viz[node] = 1;
for (list<int>::iterator it = G[node].begin(); it != G[node].end(); it++)
if (!viz[*it]) DFS(*it);
}
bool IsEulerian()
{
for (int i = 1; i <= N;i++)
if (G[i].size() % 2)
return 0;
DFS(1);
for (int i = 1; i <= N;i++)
if (!viz[i]) return 0;
return 1;
}
void DeleteRoads(int a, int b)
{
G[a].pop_front();
for (list<int>::iterator it = G[b].begin(); it != G[b].end(); it++)
if (*it == a)
{ G[b].erase(it); break; }
}
void InitEulerian(int node)
{
do
{
while (G[node].size())
{
int aux = G[node].front();
DeleteRoads(node, aux);
Queue.push(node);
node = aux;
}
int val = Queue.top();
Queue.pop();
Eu.push_front(val);
node = val;
} while (Queue.size());
}
int main()
{
freopen("elmaj.in", "r", stdin);
freopen("elmaj.out", "w", stdout);
scanf("%d%d", &N,&M);
int x, y;
for (int i = 1; i <= M; i++)
{
scanf("%d%d", &x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
if (IsEulerian())
{
InitEulerian(1);
for (list<int>::iterator it = Eu.begin(); it != Eu.end(); it++)
printf("%d ", *it);
}
else
printf("-1");
return 0;
}