Pagini recente » Cod sursa (job #60465) | Cod sursa (job #733701) | Cod sursa (job #1957016) | Cod sursa (job #433694) | Cod sursa (job #1412384)
#include <fstream>
#include <vector>
#include <stack>
#include <iostream>
#define NMax 100005
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int N,M;
vector<int> G[NMax],Sol;
stack <int> S;
int use[NMax];
void Read()
{
fin>>N>>M;
for(int i=1;i<=M;i++)
{
int x,y;
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void DFS(int nod)
{
int i, vecin;
use[nod] = 1;
for(i=0; i<G[nod].size(); i++){
vecin = G[nod][i];
if(!use[vecin]){
DFS(vecin);
}
}
}
int Check()
{
for(int i = 1; i<=N; i++)
if(G[i].size() % 2 == 1)
return 0;
DFS(1);
for(int i = 1; i<=N; i++)
if(!use[i])
return 0;
return 1;
}
void Erase(int Nod1, int Nod2)
{
G[Nod1].erase(G[Nod1].begin());
for(int i = 0; i< (int) G[Nod2].size(); i++)
if(G[Nod2][i]==Nod1)
{
G[Nod2].erase(G[Nod2].begin() + i);
break;
}
}
void Cycle(int Nod)
{
while(G[Nod].size())
{
S.push(Nod);
int Vecin = G[Nod][0];
Erase(Nod,Vecin);
Nod = Vecin;
}
}
void Solve()
{
int Nod = 1;
do
{
Cycle(Nod);
Nod = S.top(); S.pop();
Sol.push_back(Nod);
}
while(!S.empty());
}
void Print()
{
for(int i=0;i< (int) Sol.size(); i++)
fout<<Sol[i]<<" ";
fout<<"\n";
}
int main()
{
Read();
if(Check()){
Solve();
Print();
}
else
fout<<-1<<"\n";
return 0;
}